Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Height is the number of EDGES on the longest root-to-leaf path — not nodes. The recursive answer: height = 1 + max(height(left), height(right)), but with the base case set so a null child contributes −1, which makes a single leaf return 0. The clean trick most people use: treat a null node as height −1, so leaf = 1 + max(−1, −1) = 0. Either way it's postorder DFS in O(n) time and O(h) stack space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know height is measured in edges (single node = 0) and can express it as a postorder aggregation where children compute before the parent.
Where candidates slip
Returning 1 for a single node — that's the node-counted depth, not the edge-counted height HackerRank wants. Off by one on every answer.
How to stand out
State up front that height counts edges, set the null base case to −1 so leaves naturally return 0, and note this is the same recursion as Maximum Depth shifted by one.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewLongest root-to-leaf measurement?Edges or nodes?EdgesNodesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Recursive DFS — 1 + max(left, right), null = −1 (Optimal)
1Hint 1Explore hintHide hint
If you knew the height of the left subtree and the height of the right subtree, how would you get the height of the whole tree?
2Hint 2Explore hintHide hint
The height is 1 (for the edge down to a child) plus the taller of the two subtrees. What base value makes a single leaf come out as 0?
3Hint 3Explore hintHide hint
Set null → −1. Then a leaf computes 1 + max(−1, −1) = 0, exactly the edge-count definition. Recursive case: 1 + max(height(left), height(right)).
A · Core idea
Height has a naturally recursive definition: the height of a tree is one more than the height of its taller subtree, measured in edges.
The base case is the whole trick. A null child has no node and therefore contributes height −1. That negative value is deliberate: it makes a leaf node (two null children) evaluate to 1 + max(−1, −1) = 0, which is exactly the edge-count height of a leaf. If you instead returned 0 for null, a leaf would report 1 and you'd be computing node-counted depth (LeetCode 104), off by one from what HackerRank asks.
Recursive case. For a real node, ask both children for their heights, take the larger (the longest path descends through the taller subtree), and add 1 for the edge connecting this node to that subtree.
Why this is postorder. A node cannot answer until both children have reported — the combining work happens on the way back up. That bottom-up shape is the most reused tree recursion: Balanced Tree, Diameter, and Maximum Path Sum are all this same structure with extra bookkeeping.
Height vs depth in one sentence. Height counts edges (this problem, null = −1, leaf = 0); depth counts nodes (LeetCode 104, null = 0, leaf = 1). Pick the base value to match the convention and the rest of the code is identical.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,3,null,null,4,5] (1 has children 2 and 3; 3 has children 4 and 5)How to read it:Leaves return 0; node 3 returns 1; root 1 returns 1 + max(0,1) = 2.
2C · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The recursion returns up the tree. Each node waits for its children, then folds with 1 + max(...). The only knob between 'height' and 'depth' is the null base value (−1 vs 0) — choose it consciously and you'll never be off by one.
ComplexityO(n) time, O(h) space — Every node is visited once and does O(1) work (a max and an add) → O(n) time. Recursion depth equals tree height h → O(h) space: O(log n) balanced, O(n) skewed.
E · Edge cases and pitfalls6root = [1] — 1 + max(-1,-1) = 0 — a single node has height 0.Explore edge casesHide edge cases
Edge cases handled
root = [1]1 + max(-1,-1) = 0 — a single node has height 0.Left-skewed chain of 4 nodesEach level adds one edge → returns 3; recursion depth is 4 (O(n)).Perfectly balanced tree of 7 nodesTwo levels of edges → returns 2.
Pitfalls
- Returning 0 for null (gives node-counted depth, off by one from height).
- Returning 1 for a single node — that's depth, not height.
- Using min instead of max — yields the shortest path, not the longest.
Approach 2 of 2
Iterative BFS — Count Levels Minus One
1Hint 1Explore hintHide hint
Height in edges equals (number of levels) − 1. How would you count the levels of a tree without recursion?
2Hint 2Explore hintHide hint
Use a queue. Each outer iteration drains exactly one level; count how many levels you drain.
3Hint 3Explore hintHide hint
After the queue empties, subtract 1 from the level count to convert nodes-deep into edges-deep.
A · Core idea
The number of edges on the longest path is one less than the number of levels, so a level-counting BFS answers it directly.
The level-drain trick. Seed a queue with the root and a level counter at 0. Each outer-loop iteration represents one level: snapshot the queue size, dequeue exactly that many nodes while enqueuing their children, then increment the level count. When the queue empties, the count is the number of levels.
Converting to edges. Levels counts nodes-deep (root level = 1). Height counts edges, which is one fewer, so the answer is levels − 1. For a single node we drain one level and return 1 − 1 = 0, matching the edge convention.
Why snapshot the size up front. The queue grows as you enqueue children, so you must capture levelSize before the inner loop or you'd bleed into the next level. This 'capture the size, loop exactly that many times' idiom is the universal level-by-level BFS pattern.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,3,null,null,4,5]Interactive diagram
Levels counted, then minus one
level 1Three levels of nodes → height = 3 − 1 = 2 edges.
2C · Code with teaching comments
Reference implementation previewpublic int height(Node root) { if (root == null) return -1; // empty tree: -1 edges Queue<Node> queue = new LinkedList<>(); queue.offer(root); int levels = 0;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(w) spaceOpen the invariant and proofExplore the proofHide the proof
BFS gives you the level count for free; the only twist for height is subtracting 1 to convert nodes-deep into edges-deep. The same skeleton, keeping the popped values per level, becomes Level Order Traversal.
ComplexityO(n) time, O(w) space — Each node is enqueued and dequeued once → O(n) time. The queue holds at most one level, bounded by the maximum width w → O(w) space (up to O(n)).
E · Edge cases and pitfalls6root = [1] — One level drained → levels=1 → returns 0.Explore edge casesHide edge cases
Edge cases handled
root = [1]One level drained → levels=1 → returns 0.root = [1,2,null]Two levels → returns 1.Perfect tree of height hQueue peaks at the last level (~n/2 nodes) → O(n) space worst case.
Pitfalls
- Forgetting the −1 conversion and returning the node-counted depth.
- Reading queue.size() inside the inner loop — bleeds levels together.
- Incrementing levels per node instead of per level — wildly overcounts.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting nodes instead of edges
HackerRank's height is edges, so a single node is 0. Returning 0 for null makes a leaf return 1 (node-counted depth), off by one from the required answer.
Explore the code comparisonHide the code comparison
Counting nodes instead of edges
HackerRank's height is edges, so a single node is 0. Returning 0 for null makes a leaf return 1 (node-counted depth), off by one from the required answer.
Don't write this
public int height(Node root) {
if (root == null) return 0; // node-count base → off by one
return 1 + Math.max(height(root.left), height(root.right));
}Write this instead
public int height(Node root) {
if (root == null) return -1; // edge-count base
return 1 + Math.max(height(root.left), height(root.right));
}2Using min instead of max
Height follows the LONGEST root-to-leaf path. Using min returns the shortest path length, a different problem.
Explore the code comparisonHide the code comparison
Using min instead of max
Height follows the LONGEST root-to-leaf path. Using min returns the shortest path length, a different problem.
Don't write this
def height(root):
if root is None:
return -1
return 1 + min(height(root.left), height(root.right))Write this instead
def height(root):
if root is None:
return -1
return 1 + max(height(root.left), height(root.right))Revise
Carry the pattern into the interview
Pattern to remember
Postorder DFS aggregation, edge-counted (height, not depth)
Code pattern to memorize
height(node):
if node is null: return -1
return 1 + max(height(node.left), height(node.right))Rules to remember
- 1HackerRank counts edges, so a single node has height 0, not 1.
- 2The cleanest base case is
null → -1; then a leaf evaluates to1 + max(-1, -1) = 0. - 3It's postorder: both children must report before the parent can answer.
- 4Take the max of child heights (longest path), then +1 for the edge to this node.
- 5Don't confuse height (edges, this problem) with depth (nodes, LeetCode 104) — they differ by exactly 1.
Use this pattern when
- You need the height (edge count) of a tree or longest root-to-leaf path
- Any value where a node's answer is built bottom-up from its children
- A building block for Balanced Tree, Diameter, and Max Path Sum
Choose another pattern when
- You need depth in NODES → return 1 + max with null = 0 (LeetCode 104 convention)
- You need per-level node lists → that's Level Order Traversal, not a single number
- You need the path itself → carry the path, not just the count
Interview takeaway
Height is the edge-counted twin of maximum depth. The only difference from the node-counted version is the base value: null returns −1 here instead of 0. Internalize the postorder shape — children return a value, parent folds with 1 + max.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPostorder (bottom-up) aggregation, edge-counted. The height recursion is identical to the maximum-depth recursion except the null base case is −1 instead of 0, shifting every answer by one. This bottom-up shape — children return a value, parent folds with 1 + max — powers Balanced Tree, Diameter, and Max Path Sum.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximum Depth of Binary TreeSame recursion but node-counted: null returns 0, so a single node is depth 1.
- Balanced Binary TreeSame height recursion, plus check |leftHeight − rightHeight| ≤ 1 at every node.
- Diameter of Binary TreeTrack leftHeight + rightHeight at each node while the recursion returns the height upward.