Second largest node in BST
December 16, 2023
Problem #
Given the root to a binary search tree, find the second largest node in the tree.
Solution #
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def find_second_largest(root):
"""
Function to find the second largest element in a binary search tree.
:param root: Root node of the binary search tree
:return: Value of the second largest node
"""
# Helper function to find the rightmost and the parent of rightmost nodes
def find_rightmost_and_parent(node):
parent = None
while node.right:
parent = node
node = node.right
return node, parent
# Base case: if the tree is empty or has only one node
if not root or (not root.left and not root.right):
return None
# Find the rightmost (largest) node and its parent
largest, parent_of_largest = find_rightmost_and_parent(root)
# If the largest node has a left subtree, find the rightmost node in that subtree
if largest.left:
return find_rightmost_and_parent(largest.left)[0].value
# Otherwise, the second largest element is the parent of the largest element
return parent_of_largest.value
# Example usage
# Creating a simple binary search tree
# 4
# / \
# 2 6
# / / \
# 1 5 7
root = TreeNode(4, TreeNode(2, TreeNode(1)), TreeNode(6, TreeNode(5), TreeNode(7)))
find_second_largest(root)