Second max in BST

algorithm data-structures language-agnostic binary-search-tree
Michael picture Michael · Jul 11, 2012 · Viewed 19.2k times · Source

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

templatetypedef picture templatetypedef · Jul 11, 2012

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!

Related questions

Ukkonen's suffix tree algorithm in plain English

I feel a bit thick at this point. I've spent days trying to fully wrap my head around suffix tree construction, but because I don't have a mathematical background, many of the explanations elude me as they start to make …

Read More
design a stack such that getMinimum( ) should be O(1)

This is one of an interview question. You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack. For example: consider the below example case #1 5 --> TOP 1 4 6 2 …

Read More
Finding anagrams for a given word

Two words are anagrams if one of them has exactly same characters as that of the another word. Example : Anagram & Nagaram are anagrams (case-insensitive). Now there are many questions similar to this . A couple of approaches to find whether …

Read More