How Many Levels Tall Is the Tree
Solve this ProblemYou are given the root of a binary tree. Return its height: the number of nodes on the longest path that starts at the root and goes down to a leaf. An empty tree has height 0.
You can carry the current depth downward and remember the largest one you see, or let each call return the height of its own subtree and combine the two children with a max.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 (the values never affect the answer) - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Return the number of nodes on the longest downward path from the root to a leaf (the number of levels). An empty tree has 0 levels
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Carry the Depth Downward, Keep the Best
GoodGo top-down. A helper receives each node together with its depth (the root has depth 1); at every real node it updates a running "deepest so far" value, then visits the left and right children at depth + 1. When the walk ends, the deepest value seen is the number of levels. This needs a shared variable (or an extra parameter) that outlives the calls, but it is easy to follow: every node reports its own depth. It visits each node once — O(n) time, O(h) recursion space.
O(n)O(h)1class Solution {
2 private int best;
3
4 public int treeHeight(TreeNode root) {
5 best = 0;
6 dive(root, 1);
7 return best;
8 }
9
10 private void dive(TreeNode node, int depth) {
11 if (node == null) return;
12 best = Math.max(best, depth);
13 dive(node.left, depth + 1);
14 dive(node.right, depth + 1);
15 }
16}Optimal — Bottom-Up: 1 + the Taller Child
OptimalLet each call answer a single question about its own subtree: how tall is it? A missing subtree has height 0; a node is one level taller than its taller child, so its height is 1 + max(height of left, height of right). The answer for the whole tree is the height of the root. There is no shared variable and no depth parameter — the result simply flows back up the return values. Each node is visited once (O(n)); the extra space is the recursion depth, O(h). (The same value can also be found by counting levels with a queue.)
O(n)O(h)1class Solution {
2 public int treeHeight(TreeNode root) {
3 if (root == null) return 0;
4 int left = treeHeight(root.left);
5 int right = treeHeight(root.right);
6 return 1 + Math.max(left, right);
7 }
8}