Diameter of Binary Tree (LeetCode 543)
Height Return + Global Extremum: The Longest Path May Bend at Any Node
You are given the root of a binary tree. The diameter is the length of the longest path between any two nodes, measured as the number of edges on that path. The path does not have to pass through the root. Return the diameter.
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
Why It Works & Core Invariant
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
Establish initial problem boundaries and state invariants such that the valid search space is fully bounded.
lo, hi = 0, len(items) - 1| 1 | if not node: return 0 |
| 2 | left = height(node.left) |
| 3 | right = height(node.right) |
| 4 | diameter = max(diameter, left + right) |
| 5 | return 1 + max(left, right) |
Target: Diameter of Binary Tree (LeetCode 543). An empty subtree has height 0
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Maximum Depth (§4.1) 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.
🪄 Breaking Down the Code's "Magic Trick"
def height(node): nonlocal diameter if not node: return 0 left = height(node.left) right = height(node.right) diameter = max(diameter, left + right) # the path that bends here, counted in edges return 1 + max(left, right) # a parent can extend only one branch 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.
💡 Summary
When the answer is a path that may bend at any node, but a parent can only use a straight path from its child, return the straight-path value and record the bent-path value in a global. Every "longest path anywhere in the tree" problem uses this split.
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
You will see why the value a node returns (its height) and the answer it records (the path bending at it) must be different quantities.
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
Only checking the root's bend: the longest path can sit entirely inside one subtree.
Counting nodes instead of edges: every answer is off by one.
Returning left + right upward: a parent cannot extend a path that already bends.
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.
So: diameter = max(diameter, left + right); return 1 + max(left, right).
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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.
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 is off by one on every input (a single node has diameter 0). Returning left + right upward instead of 1 + max(left, right) hands the parent a path it cannot extend, because a parent can only continue down one branch.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
Diameter of Binary Tree (LeetCode 543)
Height Return + Global Extremum: The Longest Path May Bend at Any Node
You are given the root of a binary tree. The diameter is the length of the longest path between any two nodes, measured as the number of edges on that path. The path does not have to pass through the root. Return the diameter.
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
Why It Works & Core Invariant
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
Establish initial problem boundaries and state invariants such that the valid search space is fully bounded.
lo, hi = 0, len(items) - 1| 1 | if not node: return 0 |
| 2 | left = height(node.left) |
| 3 | right = height(node.right) |
| 4 | diameter = max(diameter, left + right) |
| 5 | return 1 + max(left, right) |
Target: Diameter of Binary Tree (LeetCode 543). An empty subtree has height 0
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Maximum Depth (§4.1) 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.
🪄 Breaking Down the Code's "Magic Trick"
def height(node): nonlocal diameter if not node: return 0 left = height(node.left) right = height(node.right) diameter = max(diameter, left + right) # the path that bends here, counted in edges return 1 + max(left, right) # a parent can extend only one branch 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.
💡 Summary
When the answer is a path that may bend at any node, but a parent can only use a straight path from its child, return the straight-path value and record the bent-path value in a global. Every "longest path anywhere in the tree" problem uses this split.
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
You will see why the value a node returns (its height) and the answer it records (the path bending at it) must be different quantities.
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
Only checking the root's bend: the longest path can sit entirely inside one subtree.
Counting nodes instead of edges: every answer is off by one.
Returning left + right upward: a parent cannot extend a path that already bends.
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.
So: diameter = max(diameter, left + right); return 1 + max(left, right).
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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.
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 is off by one on every input (a single node has diameter 0). Returning left + right upward instead of 1 + max(left, right) hands the parent a path it cannot extend, because a parent can only continue down one branch.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| if node is None: return 0 | if not node: return 0 | An empty subtree has height 0 |
| left_h = dfs_height_with_global(node.left, best); right_h = dfs_height_with_global(node.right, best) | left = height(node.left); right = height(node.right) | Postorder: both heights are known before combining |
| best[0] = max(best[0], left_h + right_h) | diameter = max(diameter, left + right) | The bent path at this node, in edges, is recorded but never returned |
| return 1 + max(left_h, right_h) | return 1 + max(left, right) | A parent can extend only the longer straight branch |