Three words, one recursion
Height of a node = edges on the longest downward path to a leaf. Depth is the mirror: edges from the root down to the node. Max depth / height of the tree is just the root's height.
Diameter is the longest path between any two nodes (counted in edges), and it need not pass through the root. The insight: at every node, the longest path bending there is leftHeight + rightHeight. Compute height bottom-up and, as a side effect, track the max of that sum. One pass, O(N).
// height with diameter as a side effect
height(node):
if null: return 0
L = height(node.left)
R = height(node.right)
diameter = max(diameter, L + R)
return 1 + max(L, R)
height(node):
if null: return 0
L = height(node.left)
R = height(node.right)
diameter = max(diameter, L + R)
return 1 + max(L, R)
Time Complexity
O(N)
Single postorder pass; every node computes its height and updates the diameter in O(1).
Space Complexity
O(H)
Recursion stack equals the tree height H (O(N) if skewed).
Live Visualization
Current call
On active path
Height computed
Diameter bends here
Call stack (top = current) — small teal number on each node = its height
Height of each node
L height = –
R height = –
path thru = –
diameter = 0
Step 0 / 0
Left height
–
child result
Right height
–
child result
Path through
–
L + R
This height
–
1 + max(L,R)
Hit Play to compute heights bottom-up. Switch to Diameter to track the longest bend.
✓ Done
Speed
Step-by-step trace
| # | Action | Node | L | R | Thru (L+R) | Height | Diameter |
|---|
C++ — Maximum Depth (LC 104)