Longest ZigZag Path in a Binary Tree (LeetCode 1372)
You're handed a binary tree's root. Starting from any node, walk down while flipping which side you step to at every hop — left, then right, then left, and so on — for as long as the next hop exists; count the edges that walk covers as its length. Report the greatest such length found anywhere 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
Core Insight
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
Each call is told whether it arrived by a left edge and how many alternating edges end at it. Every node is a possible end of a zigzag, so the best is updated on arrival.
if not node:
return
longest = max(longest, length)| 1 | if not node: |
| 2 | return |
| 3 | longest = max(longest, length) |
| 4 | if went_left: |
| 5 | dfs(node.right, False, length + 1) |
| 6 | dfs(node.left, True, 1) |
| 7 | else: |
| 8 | dfs(node.left, True, length + 1) |
| 9 | dfs(node.right, False, 1) |
| 10 | dfs(root.left, True, 1) |
| 11 | dfs(root.right, False, 1) |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Count Good Nodes 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.
🔑 The Key Idea in the Code
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.
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
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.
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.
Complexity & Mathematical Proof
O(N)
Look at dfs(node, went_left, length): each node is reached exactly once, because every node has exactly one incoming edge and each call recurses into each child once. Both the 'continue' and 'restart' runs are handled by those same two calls, so runs starting at every node cost nothing extra: O(1) work per node, O(N) total. Starting a fresh walk from every node instead would cost O(N · H).
O(H) Auxiliary
Only the recursion stack grows, one frame per level of the current path, so auxiliary space is the tree height H. The direction flag and length are O(1) per frame.
T(N) = N · O(1) = O(N)
Derivation Progression
N node visits
Each node is entered once, through its single parent edge.
O(1) Work Per Framemax(longest, length); two child calls
One call continues the run with length + 1, the other restarts it at 1.
O(N)
N frames with constant work each; no outer loop over starting nodes.
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 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.
Longest ZigZag Path in a Binary Tree (LeetCode 1372)
You're handed a binary tree's root. Starting from any node, walk down while flipping which side you step to at every hop — left, then right, then left, and so on — for as long as the next hop exists; count the edges that walk covers as its length. Report the greatest such length found anywhere 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
Core Insight
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
Each call is told whether it arrived by a left edge and how many alternating edges end at it. Every node is a possible end of a zigzag, so the best is updated on arrival.
if not node:
return
longest = max(longest, length)| 1 | if not node: |
| 2 | return |
| 3 | longest = max(longest, length) |
| 4 | if went_left: |
| 5 | dfs(node.right, False, length + 1) |
| 6 | dfs(node.left, True, 1) |
| 7 | else: |
| 8 | dfs(node.left, True, length + 1) |
| 9 | dfs(node.right, False, 1) |
| 10 | dfs(root.left, True, 1) |
| 11 | dfs(root.right, False, 1) |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Count Good Nodes 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.
🔑 The Key Idea in the Code
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.
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
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.
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.
Complexity & Mathematical Proof
O(N)
Look at dfs(node, went_left, length): each node is reached exactly once, because every node has exactly one incoming edge and each call recurses into each child once. Both the 'continue' and 'restart' runs are handled by those same two calls, so runs starting at every node cost nothing extra: O(1) work per node, O(N) total. Starting a fresh walk from every node instead would cost O(N · H).
O(H) Auxiliary
Only the recursion stack grows, one frame per level of the current path, so auxiliary space is the tree height H. The direction flag and length are O(1) per frame.
T(N) = N · O(1) = O(N)
Derivation Progression
N node visits
Each node is entered once, through its single parent edge.
O(1) Work Per Framemax(longest, length); two child calls
One call continues the run with length + 1, the other restarts it at 1.
O(N)
N frames with constant work each; no outer loop over starting nodes.
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 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.