Second Largest Node in Binary Search Tree

Problem

You are given the root to a binary search tree. Find the second largest node in the tree and return it. For example for the given binary search tree, return 3.

Solution

It may be noted that in the following solutions, NULL is returned if there are less than 2 nodes in the BST.

Recursive Solution

Inorder traversal traverses the BST in a sorted way. Thus, if we perform a reverse inorder traversal, we will get the largest node first and then second largest node and so on.

In the following solution k is set to 2, since we want to find the second largest node. In the reverse inorder traversal function, k is decremented every time we are at the current node (revere inorder traversal is performed by visiting right node first, then current node and then the left node). As soon as k is 0, the value of the current node is returned.

int secondLargestElement = NULL;
void reverseInorder(TreeNode* root, int &k) {
    if (root == nullptr) return;
    reverseInorder(root -> right, k);
    --k;
    if (k == 0) {
        secondLargestElement = root -> val;
        return;
    }
    reverseInorder(root -> left, k);
}

int secondLargestRecursive(TreeNode* root) {
    int k = 2;
    reverseInorder(root, k);
    return secondLargestElement;
}

• Time Complexity: $O(h)$, where $h$ is the height of the BST which can go as maximum as the number of nodes for a skewed BST.
• Space Complexity: $O(h)$ (where $h$ is the height of the BST) for the implicit stack required for recursion.

Iterative solution

For iterative solution we have to consider few cases:

• Right subtree is empty: The answer will be inorder predecessor to the root.
• Right-most node is not a leaf node: The answer will be the left child of the right most node.
• Right-most node is a leaf node: The answer will be the parent to the right-most node.

int secondLargestIterative(TreeNode* root) {
    TreeNode* prevNode;
    // empty BST
    if (!root) return NULL;
    // less than 2 nodes in the BST
    if (!root -> right and !root -> left) return NULL;
    // right subtree is empty
    if (!root -> right) {
        root = root -> left;
        while(root -> right) {
            root = root -> right;
        }
        return root -> val;
    }
    // traverse to the right most node
    while(root -> right) {
        prevNode = root;
        root = root -> right;
    }
    // empty right most node
    if (!root -> right and !root -> left) {
        return prevNode -> val;
    }
    return root -> left -> val;
}

Time Complexity: $O(h)$, where $h$ is the height of the BST which can go as maximum as the number of nodes for a skewed BST.

Space Complexity: $O(1)$.