Second Largest in a BST

Second Largest in a BST asks you to find the second-biggest value in a binary search tree. The trick is to use the one property that makes a BST special: every right step leads to a larger value, so the biggest value is always at the end of the right spine.

The slow way first

The obvious idea: do a full in-order traversal to collect every value in sorted order, then return the second-to-last one. That works, but it visits all n nodes and uses O(n) extra space for the list. We never needed most of those values.

The question to ask: where does the largest value actually live? In a BST, going right always increases the value, so the maximum is at the bottom of the right spine. We can walk straight to it and never look at the left side at all.

The idea: go right, remember the previous node

Start at the root and keep stepping to the right child. The last node with no right child is the maximum. The answer is the node we visited just before it — its in-order predecessor. So we keep a second pointer, prev, that trails one step behind cur as we walk down.

When the max is a leaf (no left subtree), prev is exactly the second largest. The walk only touches the right spine, so it is far cheaper than a full traversal.

Walk through it

Step through the animation. cur starts on the root 5 and prev is empty. Each time cur has a right child we slide prev up to where cur was and move cur right: 5 → 8 → 9. When cur reaches 9 it has no right child, so it is the maximum — and prev, sitting one step behind on 8, is the second largest.

Pseudocode

cur  = root
prev = None
while cur has a right child:
    prev = cur            # remember the node we are leaving
    cur  = cur.right      # step to the larger value
# cur is now the maximum; prev is the node just before it
return prev's value

The Python solution

def second_largest(root):
    cur = root
    prev = None
    while cur.right is not None:
        prev = cur
        cur = cur.right
    return prev.value

• cur walks down the right spine; prev always trails one node behind.
• The loop runs only while cur.right exists — each step moves to a strictly larger value.
• When the loop ends, cur has no right child, so it holds the maximum value.
• prev is the node we left on the final step — the in-order predecessor of the max, which is the second largest.
• This assumes the maximum is a leaf. If the max had a left subtree, the second largest would instead be the rightmost node of that subtree.

Complexity

We walk just the right spine, so the work is O(h) where h is the height — O(log n) for a balanced tree, O(n) only for a fully right-skewed one. And we keep just two pointers, so the extra space is O(1).

When this pattern shows up

Practice