Where does a binary search tree keep its smallest key, and what does finding it cost?
answer
- Keep walking one direction while you can
- Nothing smaller can hide anywhere else
- The stopping condition is a missing child
- One step per level, not per key
- Height, not log n, is the honest bound
basics
~20 sThe smallest key sits at the leftmost node: from the root, follow left children until one has none. That walk touches one node per level, so it costs O(h), where h is the tree's height — not constant time.
solid answer
~50 sThe minimum is the leftmost node and the maximum is the rightmost one. The argument is the invariant: any key smaller than the current node would have to live in its left subtree, so once a node has no left child, nothing smaller exists anywhere. The walk visits exactly one node per level, so both cost `O(h)` — height, not `O(1)`, and not `O(log n)` unless the tree's shape happens to make `h` logarithmic. Two things people get wrong here. First, the minimum is not "the root's left child"; it can be many levels down. Second, `O(h)` is the honest bound for **every** operation on a plain search tree — lookup, insert, delete, min, max — because they all follow one root-to-somewhere path. An implementation that needs constant-time minimum can cache a pointer to the leftmost node and maintain it on insert and delete.
go deeper
Be able to say 'leftmost node for the smallest, rightmost for the largest' and to justify it in one sentence from the ordering rule. Know that reaching it is a walk, not a constant-time read.
Explain why the walk stops at a missing left child and why that stopping condition is sufficient. State the cost as O(h) and be ready to say what h is and what it is not.
Show when the O(h) walk is worth avoiding: a hot read path that only ever needs the extremes can keep cached leftmost and rightmost pointers, maintained on insert and delete. Be able to name what those updates cost.
Frame it as an interface decision: if the workload's dominant query is 'the smallest live key', decide whether the structure should expose and maintain that pointer, and who pays the maintenance cost on every write path.
## Where the extremes live In a binary search tree the smallest key is at the **leftmost** node — reachable by starting at the root and repeatedly stepping to the left child until there is no left child left to take. Symmetrically the largest key is at the rightmost node. The proof is one line of the invariant. Suppose you are standing at node `k` and it has no left child. Every key smaller than `k` would have to be in `k`'s left subtree, by the invariant; that subtree is empty; therefore no key in that subtree is smaller. And every ancestor you walked past to get here, you left via its *left* branch, meaning `k` and everything under it is smaller than all of them. Combine the two and `k` is the global minimum. Note what this does **not** require: the tree does not have to be balanced, sorted on insert, or annotated in any way. Leftmost is the minimum in any valid search tree, however misshapen. ## The cost is O(h), and that phrasing is deliberate The walk visits exactly one node per level it descends, so it does at most `h` steps where `h` is the height of the tree. Hence `O(h)` time and `O(1)` extra space when written as a loop. Candidates routinely quote `O(log n)` here, and it is worth being precise about why that is a claim about *shape*, not about the operation. `h` is a property of the particular tree you have in hand. A tree whose nodes arrived in an order that produced a bushy shape has `h` around `log n`; a tree that ended up long and thin has `h` closer to `n`. The min walk itself does not care and does not change: it takes one step per level, whatever the number of levels turns out to be. Saying `O(h)` reports the operation's cost honestly and leaves the height as a separate question about the tree's shape. The same `O(h)` framing covers the whole basic operation set: | Operation | Cost | Path followed | |---|---|---| | lookup | O(h) | root down, one comparison per level | | insert | O(h) | root down to a missing child slot | | delete | O(h) | root down to the node, plus at most one further descent | | minimum / maximum | O(h) | root down the leftmost / rightmost spine | | floor / ceiling | O(h) | root down, tracking the best candidate | Every one of them is a single root-to-somewhere path. That is the unifying fact about this structure: it does not scan, it descends, and the descent is bounded by the height. ## Two misconceptions to kill **"The minimum is the root's left child."** Only if that child happens to have no left child of its own. In general the leftmost node can be at any depth, and in a long left-leaning tree it is the deepest node in the structure. **"Finding the minimum is O(1) because it is just the leftmost node."** This confuses *knowing where a thing is* with *getting to it*. The position is described in constant words; reaching it takes a traversal. An implementation genuinely can make it constant time — by keeping a cached pointer to the leftmost node and updating that pointer whenever an insert lands further left or a delete removes the current minimum. That is a real technique and a fine thing to mention, but it is bookkeeping the implementation pays for, not something the plain structure gives you. ## Why the minimum walk keeps showing up The leftmost walk is not just a party trick for reporting the smallest key; it is a subroutine inside other operations. The most important case is deleting a node that has two children: the replacement is the smallest key in that node's **right** subtree — its inorder successor — which is found by exactly this walk, started at the right child instead of at the root. Range and iteration operations lean on it too: the first element of an inorder iteration is the leftmost node, and iteration proceeds from there by repeatedly taking successors. It is also the shape of the correctness argument for a whole family of descents. "Go one way until you cannot" is sound here only because the invariant guarantees that the direction you are walking is the direction the answer lies in. The moment the invariant is broken, the leftmost node is no longer necessarily the minimum, and every operation built on the same reasoning inherits the error. ## What a strong answer sounds like Name the leftmost node, justify it from the invariant in one sentence, state the cost as `O(h)` and explain that `h` is a property of the tree's shape rather than a guarantee of the operation, and mention the cached-pointer option as the way real implementations get constant-time minimum when they need it.
- Can an implementation make minimum lookups constant time?Yes — cache a pointer to the leftmost node and maintain it as a side effect of mutations: an insert that lands further left replaces it, and deleting the current minimum advances it to that node's successor. You trade a little bookkeeping on every write for `O(1)` reads, which pays off when the minimum is read far more often than the tree changes.
- Why quote every operation as O(h) instead of O(log n)?Because `h` is what the algorithm actually pays: one step per level of the tree in front of you. `log n` is a claim about that tree's shape, true only when the height happens to be logarithmic in the key count. Quoting `O(h)` separates the operation's cost from the shape question rather than smuggling an assumption into the bound.
- Where does the leftmost walk appear inside other operations?Most importantly inside deletion of a two-child node: the replacement is the smallest key of that node's right subtree, found by running the same leftmost walk starting from the right child. Inorder iteration also begins at the leftmost node and steps forward from there.
saying these in an interview costs you the question
- Says the minimum is always the root's left child
- Claims min or max is O(1) in a plain search tree
- Quotes O(log n) without mentioning the tree's shape
- Thinks finding the minimum requires visiting every node
- Confuses the leftmost node with the shallowest node