Tree Height
EasyTreesFree
Problem
Given the root of a binary tree, return its height: the number of nodes on the longest path from the root down to a leaf.
An empty tree has height 0.
Example 1
- Input:
- root = [3, 9, 20, null, null, 15, 7]
- Output:
- 3
The path 3 → 20 → 15 has three nodes.
Example 2
- Input:
- root = [1, null, 2]
- Output:
- 2
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -100 ≤ node.val ≤ 100
Hint
Show the first hint
How does the height of a tree relate to the heights of its two subtrees?
Walkthrough
How to approach it
01Clarify before coding
- Height counted in nodes or edges? Nodes: a single node has height 1, an empty tree 0.
- Can the tree be very unbalanced? Yes, up to 10^4 nodes in a line, so think about recursion depth.
02Brute force
Enumerate every root-to-leaf path, measure each and keep the longest.
Cost: Fine in time if done by DFS, but storing paths costs O(n·h) memory for nothing: only the length matters.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.