Longest ZigZag Path in a Binary Tree
Longest ZigZag Path in a Binary Tree: a zigzag path alternates direction at every step. Return the length of the longest one, measured in edges.
- The number of nodes is in the range [1, 5 * 10⁴].
- 1 <= Node.val <= 100
Intuition
A zigzag is defined by where you came from. Carry two facts down the recursion — the direction of the last move and how long the current run is — and the rule becomes local: continue the other way to extend, or start a fresh run of length 1 by going the same way.
When a path property depends on how you arrived, push that arrival state down as a DFS parameter rather than trying to reconstruct it. Direction-plus-length is the reusable shape — the same technique handles Longest Univalue Path and Binary Tree Maximum Path Sum, which carry different state for the same reason.
Approach
Before reading on: standing at a node, what two pieces of information do you need in order to know whether stepping left extends the zigzag or restarts it? Aim for O(n).
State is direction plus length
At each node you need to know two things: which way the previous step went, and how many edges the current zigzag has accumulated. Given those, the decision is mechanical. If the last move was left, then going right continues the alternation and the length becomes length + 1; going left again breaks it, so a new run begins at length 1. Symmetrically for the other direction. This is why the DFS carries parameters rather than returning a value.
Every node is a potential start
The longest zigzag need not begin at the root — it can start anywhere. Rather than launching a separate search from every node, note that the 'break the alternation' case already restarts a run of length 1 at that node, so all possible starting points are explored naturally by the same traversal. Update a global maximum at every visit and the answer accumulates without extra passes.
Counting edges, not nodes
The problem measures length in edges, so a single node has length 0 and a path visiting two nodes has length 1. Start the recursion with length 0 at the root, and increment only when a move is made. Getting this off by one is the most common source of a wrong answer here. Each node is visited twice at most — once from each direction — giving O(n) time and O(h) recursion space.
Solution & live demo
Common pitfalls
Counting nodes instead of edges
dfs(root, True, 1)
dfs(root, True, 0)
Length is measured in edges, so a lone node scores 0. Seeding with 1 inflates every answer by exactly one, which passes no test case.
Not restarting on a same-direction move
dfs(node.left, True, length + 1) # when arriving from the left
dfs(node.left, True, 1)
Moving the same way twice breaks the alternation, so the run ends and a new one begins at that node. Extending it instead reports straight chains as valid zigzags.
Only searching from the root
dfs(root, True, 0) return self.best
dfs(root, True, 0) dfs(root, False, 0)
The first call fixes an arrival direction at the root, exploring only half the possibilities. Both initial directions must be seeded, or paths beginning with the other move are never considered.
Edge cases
No edges exist, so the answer is 0.
Every step alternates and the length equals the depth minus one.
The direction never alternates, so each step restarts at 1 and the answer is 1.
The restart case seeds a run of 1 at every node, so interior starts are covered.
Recursion depth reaches O(n); on very deep trees an iterative stack avoids overflow.