Minimum and Maximum in a BST

Minimum and Maximum in a BST is a tiny problem that rewards you for knowing the data structure. A binary search tree keeps its values sorted by shape, so the answer is just a short walk — no comparisons, no full traversal.

The slow way first

If you forget it is a BST, you might traverse every node and track the smallest and largest value you see. That works on any tree, but it is O(n) — you touch all n nodes. For a balanced BST that is wasteful: the structure already sorts the values for you, and you are throwing that information away.

The question to ask: where does the BST rule put the smallest and largest values? Everything in a left subtree is smaller than its parent, so the smallest value can only be the leftmost node. By the mirror argument, the largest is the rightmost node.

The idea: follow one direction to the extreme

To find the minimum, start at the root and keep moving to the left child until there is no left child left. To find the maximum, do the same toward the right child. Each walk only visits one node per level, so it costs O(h), the height of the tree.

The key insight: in a BST you never compare values to find the extremes. The shape of the tree already encodes the order, so you just slide down one side.

Walk through it

Step through the animation. The min pointer starts at the root (8) and follows left children: 8 → 3 → 1, then stops because 1 has no left child. The max pointer starts at the root again and follows right children: 8 → 10 → 14, then stops because 14 has no right child. Notice 14 still has a left child (13), but we ignore left subtrees entirely when chasing the maximum.

Pseudocode

find_min(root):
    node = root
    while node has a left child:
        node = node.left          # smaller values are always left
    return node.value             # leftmost node
 
find_max(root):
    node = root
    while node has a right child:
        node = node.right         # larger values are always right
    return node.value             # rightmost node

The Python solution

def find_min(root):
    node = root
    while node.left is not None:
        node = node.left
    return node.val
 
def find_max(root):
    node = root
    while node.right is not None:
        node = node.right
    return node.val

• node = root starts each walk at the top of the tree.
• For the minimum, lines 3-4 keep stepping into node.left as long as one exists.
• When node.left is None, the loop stops — node is the leftmost node, so node.val is the smallest value.
• For the maximum, lines 9-10 mirror that, stepping into node.right until there is no right child.
• The rightmost node holds the largest value.

Complexity

We use only a single pointer, so the extra space is O(1). The time is O(h) — O(log n) for a balanced tree, but still O(n) in the worst case of a tree that degenerates into a chain.

When this pattern shows up

Practice