Second max in BST

Question

This is an interview question. Find the second max in BST.

The max element is the rightmost leaf in the BST. The second max is either its parent or its left child. So the solution is to traverse the BST to find the rightmost leaf and check its parent and left child.

Does it make sense?

Answer 1

No, that's wrong. Consider this BST:

        137        /       42        \         99 

Here, the second-to-max value is the rightmost child of the left child of the max value. Your algorithm will need to be updated so that you check the parent of the max value, or the rightmost subchild of the left child of the max.

Also, note that the max is not necessarily the rightmost leaf node, it's the node at the bottom of the right spine of the tree. Above, 137 is not a leaf.

Hope this helps!

Answer 2

Recall that you can list the nodes of a BST in reverse order by doing a modified inorder traversal where you explore the right subtree first. This leads to a simple algorithm:

Node rightmost = findRightmostNode(root) if (rightmost.left != null) {     return findRightmostNode(rightmost.left) else{     return rightmost.parent } 

It would return null if the tree has only one element.

Answer 3

public static int findSecondLargestValueInBST(Node root)
    {
        int secondMax;
        Node pre = root;
        Node cur = root;
        while (cur.Right != null)
        {
            pre = cur;
            cur = cur.Right;
        }
        if (cur.Left != null)
        {
            cur = cur.Left;
            while (cur.Right != null)
                cur = cur.Right;
            secondMax = cur.Value;
        }
        else
        {
            if (cur == root && pre == root)
                //Only one node in BST
                secondMax = int.MinValue;
            else
                secondMax = pre.Value;
        }
        return secondMax;
    }

Answer 4

Much easier iterative approach with Time complexity O(logN) and Space complexity O(1)

public static void main(String[] args) {    
        BinaryTreeNode result=isBinarySearchTree.secondLargest(rootNode);

            System.out.println(result.data);
        }

        private BinaryTreeNode secondLargest(BinaryTreeNode node) {

            BinaryTreeNode prevNode=null; //2nd largest Element
            BinaryTreeNode currNode=node;
            if(null == currNode)
                return prevNode;

            while(currNode.right != null){
                prevNode=currNode;
                currNode=currNode.right;
            }
            if(currNode.left != null){
                currNode=currNode.left;
                while(currNode.right != null){
                    currNode=currNode.right;
                }
                prevNode=currNode;
            }

            return prevNode;

        }