Return the height of a binary tree: the number of edges on the longest path
from the root down to a leaf. By convention an empty tree has height -1 and a
single node has height 0.
howHigh(root)
Input format: level-order with x for missing children.
3 9 20 x x 15 7 // → 2
1 2 x 3 // → 2
5 // → 0
(empty) // → -1
Height measures how far the tree extends along its longest branch, in edges. The trap isn't the recursion — it's the convention: height is edges, not node count, and an empty tree has height -1, not 0. Getting the base case wrong quietly produces off-by-one errors everywhere else.
For any node: what's the height of the subtree rooted here? It depends only on the taller of its two subtrees — the shorter branch is irrelevant, since the longest path through this node goes down whichever side reaches deeper. So: take the height of each subtree, use the larger, and add 1 for the edge down to it.
Work backwards from a leaf: it has no edges below it, so its height must be 0. Its children are both empty subtrees. Using the rule, a leaf's height is 1 + max(left, right) — for that to equal 0, an empty subtree must contribute -1, since 1 + max(-1, -1) = 0. So -1 isn't arbitrary — it's exactly the value that makes the general formula correct at the smallest case. Good general technique: work out what base-case value makes the formula correct at the simplest real case, rather than guessing.
Height asks about the longest path to a leaf, so only the deeper subtree matters — the shallower one's leaves are reachable via a shorter path and never determine the overall height. Contrast with tree-sum, where every subtree's contribution is added; here, only the extremal one matters.
Every node's height is computed once and reused by its parent, so total work is proportional to the number of nodes, with recursion memory bounded by the tree's own height.
def how_high(root):
if root is None:
return -1
return 1 + max(how_high(root.left), how_high(root.right))
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.