Return the smallest value in a non-empty binary tree. (The tree is not necessarily a binary search tree, so you must inspect every node.)
treeMinValue(root)
Input format: level-order with x for missing children. Assume at least one
node.
3 11 4 x x 2 1 // → 1
5 5 5 // → 5
-2 -7 -1 // → -7
It's tempting to assume tree problems get a shortcut from the tree's shape — but this one rules that out: it's not a binary search tree, so smaller values aren't guaranteed to live in any particular direction. The minimum could be anywhere, so the only reliable way to find it is to check every node.
For any node, the smallest value in its subtree is one of three candidates: this node's own value, the smallest in the left subtree, or the smallest in the right subtree — those three regions are everything rooted here. The answer is the minimum of those three.
The tricky part is the base case. Unlike counting or summing, where an empty subtree contributes a neutral value (0), an empty subtree has no value to offer a minimum comparison, and there's no safe "neutral" number — any pick could be smaller than every real value in the tree. The clean fix: only recurse into a child that actually exists, and skip missing ones when combining candidates.
In a true binary search tree, the minimum is always the leftmost node, so you could ignore the right subtree entirely and just walk left. Here that guarantee doesn't hold, so skipping the right subtree — or skipping the comparison against the current node — could easily produce a wrong answer. Knowing which structural guarantees a problem does and doesn't give you is one of the most common ways tree problems catch people out.
Since every node must be inspected (no way to prune), work is proportional to the number of nodes, and recursion memory is bounded by the tree's height.
def tree_min_value(root):
m = root.val
if root.left is not None:
lm = tree_min_value(root.left)
if lm < m:
m = lm
if root.right is not None:
rm = tree_min_value(root.right)
if rm < m:
m = rm
return m
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.