Diameter of Binary Tree (LeetCode 543)
You're handed a binary tree's root. Somewhere in that tree there's a longest possible walk between two nodes — not necessarily passing through the root — and its diameter is simply how many edges that walk crosses. Report that edge count.
Worked Examples
root = [1,2,3,4,5]3root = [1,2]1⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 104].-100 <= Node.val <= 100
Core Insight
Every path has one highest node where it bends. At each node, the longest path bending there has height(left) + height(right) edges. Record that in a global, but return only 1 + max(left, right), because a parent can extend just one straight branch.
Real-World Scenario & Production Applications
Worst-case hop count between two devices in a tree-shaped network, the longest chain between any two people in an org chart, the widest span of a river delta.
Subproblems & Recurrence Decomposition3 Phases
A null child contributes no nodes to any downward path.
if not node:
return 0| 1 | if not node: |
| 2 | return 0 |
| 3 | left = height(node.left) |
| 4 | right = height(node.right) |
| 5 | diameter = max(diameter, left + right) |
| 6 | return 1 + max(left, right) |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Maximum Depth returns one number per subtree. Diameter keeps that exact return value but asks a second question at every node: "if the longest path bent right here, how long would it be?" The return value and the answer are different quantities, which is why the answer lives in a separate global variable.
📏 The Analogy: Measuring the Widest Span of a River Delta
A surveyor maps a river delta that splits into channels like a tree. At every fork they ask the two branches below, "how far do you reach downstream?" The widest span through this fork is the left reach plus the right reach, and the surveyor notes it if it beats the record. But when reporting upward to the next fork, a channel can only continue in one direction, so the fork reports just its longer reach plus the one step up to its parent.
🔑 The Key Idea in the Code
The two lines after the recursive calls answer two different questions. left + right is the best path that bends at this node; it goes into the global record and is never returned. 1 + max(left, right) is the best path a parent could extend; it is returned and never recorded. Mixing them up is the whole bug class of this problem.
Checking only the root's bend: Checking only the bend at the root misses a longer path that sits entirely inside one subtree (
[1,2,null,3,4,5,null,null,6]has diameter 4, but the root's bend is only 3).Counting nodes instead of edges: Counting nodes instead of edges is off by one on every input (a single node has diameter 0).
Returning the bent path upward: Returning
left + rightupward instead of1 + max(left, right)hands the parent a path it cannot extend, because a parent can only continue down one branch.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Longest path between any two nodes, measured in edges, not required to pass through the root.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the longest path bending at a node has exactly height(left) + height(right) edges.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I write
height(node)returning 0 for None. For a real node I get the left and right heights, update a globaldiameterwithleft + right, which is the number of edges on the path that bends here, and return1 + max(left, right). After one call on the root the global holds the answer. That'sO(N)time and O(H) stack space.
Complexity & Mathematical Proof
O(N)
Look at height(node): each node is visited once, makes two child calls, updates diameter with left + right, and returns 1 + max(left, right) — O(1) work per node, O(N) total. Computing heights separately at every node instead would cost O(N^2) on a skewed tree.
O(H) Auxiliary
Only the recursion stack grows, one frame per level of the current path, so auxiliary space is the tree height H. diameter is a single integer.
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Derivation Progression
N node visits
Every node is entered once, after both child heights are known.
O(1) Work Per Framemax(diameter, left + right); 1 + max(left, right)
One comparison records the bend, one returns the straight branch.
O(N)
N frames with constant work each.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in a balanced tree, N in a skewed tree)
Memory Architecture & Bounds
O(H) recursion frames
O(1) global best
O(1) returns one integer
Boundary Best / Worst Cases
time with stack on a balanced tree.
time.
time with stack on a skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest path between any two nodes", "may or may not pass through the root", "number of edges". Bottom-up height return with a global answer: each node returns its height, and separately updates a global best with the path that bends at it.
. One postorder pass: time.
Diameter of Binary Tree (LeetCode 543)
You're handed a binary tree's root. Somewhere in that tree there's a longest possible walk between two nodes — not necessarily passing through the root — and its diameter is simply how many edges that walk crosses. Report that edge count.
Worked Examples
root = [1,2,3,4,5]3root = [1,2]1⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 104].-100 <= Node.val <= 100
Core Insight
Every path has one highest node where it bends. At each node, the longest path bending there has height(left) + height(right) edges. Record that in a global, but return only 1 + max(left, right), because a parent can extend just one straight branch.
Real-World Scenario & Production Applications
Worst-case hop count between two devices in a tree-shaped network, the longest chain between any two people in an org chart, the widest span of a river delta.
Subproblems & Recurrence Decomposition3 Phases
A null child contributes no nodes to any downward path.
if not node:
return 0| 1 | if not node: |
| 2 | return 0 |
| 3 | left = height(node.left) |
| 4 | right = height(node.right) |
| 5 | diameter = max(diameter, left + right) |
| 6 | return 1 + max(left, right) |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Maximum Depth returns one number per subtree. Diameter keeps that exact return value but asks a second question at every node: "if the longest path bent right here, how long would it be?" The return value and the answer are different quantities, which is why the answer lives in a separate global variable.
📏 The Analogy: Measuring the Widest Span of a River Delta
A surveyor maps a river delta that splits into channels like a tree. At every fork they ask the two branches below, "how far do you reach downstream?" The widest span through this fork is the left reach plus the right reach, and the surveyor notes it if it beats the record. But when reporting upward to the next fork, a channel can only continue in one direction, so the fork reports just its longer reach plus the one step up to its parent.
🔑 The Key Idea in the Code
The two lines after the recursive calls answer two different questions. left + right is the best path that bends at this node; it goes into the global record and is never returned. 1 + max(left, right) is the best path a parent could extend; it is returned and never recorded. Mixing them up is the whole bug class of this problem.
Checking only the root's bend: Checking only the bend at the root misses a longer path that sits entirely inside one subtree (
[1,2,null,3,4,5,null,null,6]has diameter 4, but the root's bend is only 3).Counting nodes instead of edges: Counting nodes instead of edges is off by one on every input (a single node has diameter 0).
Returning the bent path upward: Returning
left + rightupward instead of1 + max(left, right)hands the parent a path it cannot extend, because a parent can only continue down one branch.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Longest path between any two nodes, measured in edges, not required to pass through the root.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the longest path bending at a node has exactly height(left) + height(right) edges.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I write
height(node)returning 0 for None. For a real node I get the left and right heights, update a globaldiameterwithleft + right, which is the number of edges on the path that bends here, and return1 + max(left, right). After one call on the root the global holds the answer. That'sO(N)time and O(H) stack space.
Complexity & Mathematical Proof
O(N)
Look at height(node): each node is visited once, makes two child calls, updates diameter with left + right, and returns 1 + max(left, right) — O(1) work per node, O(N) total. Computing heights separately at every node instead would cost O(N^2) on a skewed tree.
O(H) Auxiliary
Only the recursion stack grows, one frame per level of the current path, so auxiliary space is the tree height H. diameter is a single integer.
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Derivation Progression
N node visits
Every node is entered once, after both child heights are known.
O(1) Work Per Framemax(diameter, left + right); 1 + max(left, right)
One comparison records the bend, one returns the straight branch.
O(N)
N frames with constant work each.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in a balanced tree, N in a skewed tree)
Memory Architecture & Bounds
O(H) recursion frames
O(1) global best
O(1) returns one integer
Boundary Best / Worst Cases
time with stack on a balanced tree.
time.
time with stack on a skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest path between any two nodes", "may or may not pass through the root", "number of edges". Bottom-up height return with a global answer: each node returns its height, and separately updates a global best with the path that bends at it.
. One postorder pass: time.