Free lessonsBinary search trees · Stage 0 · Search and insert · Step 2

Minimum value in BST

Walk left until there are no more left children; the leftmost node is the minimum. About 7 minutes.

All smaller keys are on the left

Because every left child is smaller than its parent, the smallest key in any non-empty BST is always found by following left links as far as you can go. You never need to look right.

It is like finding the first word in a dictionary: just go to the very first page, and don't bother with the rest.

Going left: always leads toward smaller values.

Where to stop: at the first node that has no left child.

Where's the smallest value?

Everything smaller than 8 lives on its left. So go left.

Move 1 of 3

Iterative vs recursive

You can write this with a simple loop: start at the root, and while the current node has a left child, step onto it. It uses almost no extra memory and only visits the nodes along the left edge of the tree.

An empty tree has no smallest value, so return minus one.

Constant memory: a simple pointer loop uses no call stack.

Empty tree: if the root is empty, answer minus one.

In code

if not root:
    return -1
curr = root
while curr.left:
    curr = curr.left
return curr.val

Quick check

In a BST with 100 nodes, what is the maximum number of nodes visited to find the minimum?

AThe height of the tree (at most 100)
BAll 100 nodes
CAlways 1 node

Show the answer

The height of the tree (at most 100). You only follow one downward branch (the left spine), visiting at most height nodes.

Your problem

Minimum value in BST

Given the root of a binary search tree (BST), return the minimum value stored in the tree. If the tree is empty (root is null), return -1.

Example

root = [4, 2, 7, 1, 3] → 1

0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding