Longest ZigZag Path in a Binary Tree (LeetCode 1372)
Top-Down Direction State: Turning Extends the Run, Going Straight Restarts It
You are given the root of a binary tree. A ZigZag path starts at any node, first moves to either its left or right child, and then keeps alternating direction (left, right, left, ... or right, left, right, ...) for as long as the next child exists. Its length is the number of edges it uses, so a single node has length 0. Return the length of the longest ZigZag path in the tree.
Worked Examples
root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]3root = [1,1,1,null,1,null,null,1,1,null,1]4root = [1]0⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 5 * 104].1 <= Node.val <= 100
Why It Works & Core Invariant
Pass the arrival direction and current run length down. From each node, the child that turns continues the run with length + 1, and the child in the same direction starts a new run of length 1. Both calls always happen, so runs starting at every node are covered in one pass.
Real-World Scenario & Production Applications
Longest alternating decision sequence in a binary decision tree, longest run of alternating left/right moves in a branching route.
Subproblems & Recurrence Decomposition3 Phases
At the start of each level iteration, freeze level_size = len(queue) to isolate the current depth ring from newly appended child nodes.
queue = deque([root])
while queue:
level_size = len(queue) # Freeze ring count
current_level = []| 1 | if not node: return |
| 2 | longest = max(longest, length) |
| 3 | if went_left: dfs(node.right, False, length + 1); dfs(node.left, True, 1) |
| 4 | else: dfs(node.left, True, length + 1); dfs(node.right, False, 1) |
| 5 | dfs(root.left, True, 1); dfs(root.right, False, 1) |
Target: Longest ZigZag Path in a Binary Tree (LeetCode 1372). Each call knows the arrival direction and the current run length
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
Count Good Nodes (§4.4) passes the path's maximum down to each child. ZigZag passes down something smaller but stranger: which way you just came from, and how long your current alternating run is. Each node decides its children's state without ever looking back up.
⚡ The Analogy: A Ski Slalom Where Every Gate Must Switch Sides
A skier runs a slalom course laid out like a tree of gates. A run only counts while each gate is passed on the opposite side from the one before. At every gate the skier knows two things: which side they took the last gate on, and how many alternating gates they have strung together. Switching sides extends the run by one. Taking the same side twice doesn't end the day; it simply starts a fresh run that already counts that one gate.
🪄 Breaking Down the Code's "Magic Trick"
def dfs(node, went_left, length): nonlocal longest if not node: return longest = max(longest, length) if went_left: dfs(node.right, False, length + 1) # turn: the zigzag grows dfs(node.left, True, 1) # same direction: a new zigzag starts at this edge else: dfs(node.left, True, length + 1) dfs(node.right, False, 1) Every node launches both options at once: the child that continues the zigzag inherits length + 1, and the child that breaks it starts over at 1. Because both calls always happen, zigzags starting at every node in the tree are explored in the same single pass, with no outer loop over starting points.
💡 Summary
When a path's validity depends on the direction of the previous step, pass that direction down as a parameter together with the current run length, and let every node spawn both the "continue" and the "restart" branch. One top-down pass then covers runs that start anywhere in the tree.
Restarting at 0 instead of 1: Restarting at 0 instead of 1 undercounts every run that starts below the root (
[1,2,null,3,null,null,4]has answer 2, but a reset to 0 reports 1).Only following zigzags from the root: Only following zigzags that start at the root misses runs that start deeper.
Counting nodes instead of edges: A single node has length 0, because length counts edges, not nodes.
4-Phase Thought Process Model
You will see how passing the arrival direction and run length down lets one pass cover zigzags starting anywhere.
Pattern Recognition Signals
The 10-second spot
Longest path that alternates left and right, starting at any node, measured in edges.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: length counts the alternating edges ending at this node; turning adds one, repeating a direction resets to 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Resetting to 0 instead of 1: the edge that breaks the old run is the first edge of the new one.
Only starting from the root: zigzags can begin at any node.
Counting nodes: a single node has length 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I call
dfs(node, went_left, length), which returns on None and updates a globallongest. If I arrived by a left edge, the right child continues the zigzag withlength + 1and the left child starts a new one with 1; otherwise it's the mirror image. I seed it withdfs(root.left, True, 1)anddfs(root.right, False, 1). Every node is visited once:O(N)time, O(H) stack.
So: record length; if you arrived by a left edge, go right with length + 1 and left with 1 (and the mirror image otherwise).
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 ZigZag path"**, **"alternate left and right"**, **"start from any node"**. Top-down parameter passing with a direction state: each call is told which way it arrived and how long the current alternating run is.
. One pass: time.
Restarting at 0 instead of 1 undercounts every run that starts below the root ([1,2,null,3,null,null,4] has answer 2, but a reset to 0 reports 1). Only following zigzags that start at the root misses runs that start deeper. A single node has length 0, because length counts edges, not nodes.
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.
Longest ZigZag Path in a Binary Tree (LeetCode 1372)
Top-Down Direction State: Turning Extends the Run, Going Straight Restarts It
You are given the root of a binary tree. A ZigZag path starts at any node, first moves to either its left or right child, and then keeps alternating direction (left, right, left, ... or right, left, right, ...) for as long as the next child exists. Its length is the number of edges it uses, so a single node has length 0. Return the length of the longest ZigZag path in the tree.
Worked Examples
root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]3root = [1,1,1,null,1,null,null,1,1,null,1]4root = [1]0⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 5 * 104].1 <= Node.val <= 100
Why It Works & Core Invariant
Pass the arrival direction and current run length down. From each node, the child that turns continues the run with length + 1, and the child in the same direction starts a new run of length 1. Both calls always happen, so runs starting at every node are covered in one pass.
Real-World Scenario & Production Applications
Longest alternating decision sequence in a binary decision tree, longest run of alternating left/right moves in a branching route.
Subproblems & Recurrence Decomposition3 Phases
At the start of each level iteration, freeze level_size = len(queue) to isolate the current depth ring from newly appended child nodes.
queue = deque([root])
while queue:
level_size = len(queue) # Freeze ring count
current_level = []| 1 | if not node: return |
| 2 | longest = max(longest, length) |
| 3 | if went_left: dfs(node.right, False, length + 1); dfs(node.left, True, 1) |
| 4 | else: dfs(node.left, True, length + 1); dfs(node.right, False, 1) |
| 5 | dfs(root.left, True, 1); dfs(root.right, False, 1) |
Target: Longest ZigZag Path in a Binary Tree (LeetCode 1372). Each call knows the arrival direction and the current run length
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
Count Good Nodes (§4.4) passes the path's maximum down to each child. ZigZag passes down something smaller but stranger: which way you just came from, and how long your current alternating run is. Each node decides its children's state without ever looking back up.
⚡ The Analogy: A Ski Slalom Where Every Gate Must Switch Sides
A skier runs a slalom course laid out like a tree of gates. A run only counts while each gate is passed on the opposite side from the one before. At every gate the skier knows two things: which side they took the last gate on, and how many alternating gates they have strung together. Switching sides extends the run by one. Taking the same side twice doesn't end the day; it simply starts a fresh run that already counts that one gate.
🪄 Breaking Down the Code's "Magic Trick"
def dfs(node, went_left, length): nonlocal longest if not node: return longest = max(longest, length) if went_left: dfs(node.right, False, length + 1) # turn: the zigzag grows dfs(node.left, True, 1) # same direction: a new zigzag starts at this edge else: dfs(node.left, True, length + 1) dfs(node.right, False, 1) Every node launches both options at once: the child that continues the zigzag inherits length + 1, and the child that breaks it starts over at 1. Because both calls always happen, zigzags starting at every node in the tree are explored in the same single pass, with no outer loop over starting points.
💡 Summary
When a path's validity depends on the direction of the previous step, pass that direction down as a parameter together with the current run length, and let every node spawn both the "continue" and the "restart" branch. One top-down pass then covers runs that start anywhere in the tree.
Restarting at 0 instead of 1: Restarting at 0 instead of 1 undercounts every run that starts below the root (
[1,2,null,3,null,null,4]has answer 2, but a reset to 0 reports 1).Only following zigzags from the root: Only following zigzags that start at the root misses runs that start deeper.
Counting nodes instead of edges: A single node has length 0, because length counts edges, not nodes.
4-Phase Thought Process Model
You will see how passing the arrival direction and run length down lets one pass cover zigzags starting anywhere.
Pattern Recognition Signals
The 10-second spot
Longest path that alternates left and right, starting at any node, measured in edges.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: length counts the alternating edges ending at this node; turning adds one, repeating a direction resets to 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Resetting to 0 instead of 1: the edge that breaks the old run is the first edge of the new one.
Only starting from the root: zigzags can begin at any node.
Counting nodes: a single node has length 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I call
dfs(node, went_left, length), which returns on None and updates a globallongest. If I arrived by a left edge, the right child continues the zigzag withlength + 1and the left child starts a new one with 1; otherwise it's the mirror image. I seed it withdfs(root.left, True, 1)anddfs(root.right, False, 1). Every node is visited once:O(N)time, O(H) stack.
So: record length; if you arrived by a left edge, go right with length + 1 and left with 1 (and the mirror image otherwise).
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 ZigZag path"**, **"alternate left and right"**, **"start from any node"**. Top-down parameter passing with a direction state: each call is told which way it arrived and how long the current alternating run is.
. One pass: time.
Restarting at 0 instead of 1 undercounts every run that starts below the root ([1,2,null,3,null,null,4] has answer 2, but a reset to 0 reports 1). Only following zigzags that start at the root misses runs that start deeper. A single node has length 0, because length counts edges, not nodes.
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 |
|---|---|---|
| def dfs_direction_state(node, went_left, length, best) | def dfs(node, went_left, length) | Each call knows the arrival direction and the current run length |
| best[0] = max(best[0], length) | longest = max(longest, length) | Every node is a possible end of a zigzag |
| dfs_direction_state(node.right, False, length + 1, best) | dfs(node.right, False, length + 1) | Alternating extends the run by one edge |
| dfs_direction_state(node.left, True, 1, best) | dfs(node.left, True, 1) | A new run starts, and its first edge already counts |
| (caller) dfs_direction_state(root.left, True, 1, best); dfs_direction_state(root.right, False, 1, best) | dfs(root.left, True, 1); dfs(root.right, False, 1) | The root's two edges each start a run of length 1 |