Second largest node in BST

Second largest node in BST

December 16, 2023
graph, BST

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)))