Introduction

Finding the second maximum in a binary search tree is easier than it first appears because BST ordering already tells you where the largest values live. The maximum value is the rightmost node, so the second maximum is either that node's parent or the maximum value inside the rightmost node's left subtree.

Use The BST Property

In a BST:

• larger values are always found by moving right
• smaller values are always found by moving left

That means the maximum value is the node reached by following right pointers until there are no more.

The second maximum depends on what that maximum node looks like.

Two Cases For The Answer

There are exactly two structural cases.

1. The maximum node has a left subtree. Then the second maximum is the rightmost node of that left subtree.
2. The maximum node has no left subtree. Then the second maximum is its parent.

That logic avoids traversing the whole tree.

Iterative Python Example

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def second_max(root: Node) -> int:
9    if root is None or (root.left is None and root.right is None):
10        raise ValueError("tree must contain at least two nodes")
11
12    parent = None
13    current = root
14
15    while current.right is not None:
16        parent = current
17        current = current.right
18
19    if current.left is not None:
20        current = current.left
21        while current.right is not None:
22            current = current.right
23        return current.value
24
25    return parent.value

This runs in O(h) time, where h is the tree height, because it follows only one path down the tree.

Example Walkthrough

Consider this tree:

1        20
2       /  \
3     10    30
4          /  \
5        25    40

The maximum is 40. It has no left subtree, so the second maximum is its parent, 30.

Now consider:

1        20
2       /  \
3     10    40
4           /
5         35
6           \
7            37

The maximum is 40, but it has a left subtree. The rightmost node in that left subtree is 37, so the second maximum is 37.

Why Full Traversal Is Unnecessary

A beginner solution often performs an in-order traversal, stores all values, and picks the second-to-last one.

1def inorder(node):
2    if node:
3        yield from inorder(node.left)
4        yield node.value
5        yield from inorder(node.right)

That works, but it uses more time and memory than needed if your only goal is the second-largest value. The BST property already narrows the search to the right spine and possibly one left subtree.

Recursive Version

If you prefer recursion, the same two-case logic still applies.

1def second_max_recursive(node: Node) -> int:
2    if node is None or (node.left is None and node.right is None):
3        raise ValueError("tree must contain at least two nodes")
4
5    if node.right is None:
6        current = node.left
7        while current.right is not None:
8            current = current.right
9        return current.value
10
11    if node.right.left is None and node.right.right is None:
12        return node.value
13
14    return second_max_recursive(node.right)

The iterative version is often easier to explain in interviews, but either is fine if the edge cases are handled correctly.

Duplicates Change The Definition

This topic is simplest when the BST stores unique keys. If duplicates are allowed, you need to decide whether "second max" means:

• the second-largest distinct value, or
• simply the second node in descending order

Those are not the same when the maximum value appears multiple times.

Common Pitfalls

The biggest mistake is assuming the second maximum is always the parent of the maximum node. That fails when the maximum node has a left subtree. Another is forgetting the minimum-size edge case; a one-node tree has no second maximum. Developers also often solve the problem with a full traversal even though the BST property gives a more direct O(h) approach.

Summary

• The maximum in a BST is the rightmost node.
• If that node has a left subtree, the second maximum is the rightmost node in that subtree.
• Otherwise, the second maximum is the parent of the maximum node.
• The problem can be solved in O(h) time without traversing the whole tree.
• Handle small trees and duplicate-key semantics explicitly.