TL;DR
Tree DP with two states per node — (zigzag going left, zigzag going right) — in one post-order pass: O(n) time, O(h) space.
A zigzag path alternates direction at every step. The following path has length 3 (three edges), turning right, left, right:
graph TD
A -->|right| B
B -->|left| C
C -->|right| D
Approach 1 — Brute force (recompute from every node)
Intuition: from each node, and for each starting direction, walk the (deterministic) zigzag downward counting edges. A zigzag path is forced once you pick a start and a direction — after left you must go right, and so on — so following it is a simple loop. Take the maximum over all nodes and both directions.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def longestZigZag(root: "TreeNode") -> int:
best = 0
def walk(node: "TreeNode", go_left: bool) -> int:
length = 0
while node:
nxt = node.left if go_left else node.right
if nxt is None:
break
length += 1
node = nxt
go_left = not go_left
return length
def visit(node: "TreeNode") -> None:
nonlocal best
if not node:
return
best = max(best, walk(node, True), walk(node, False))
visit(node.left)
visit(node.right)
visit(root)
return best
Complexity: O(n · h) time (each of n nodes launches a walk up to the tree height h), O(h) recursion depth. For a skewed tree that is O(n^2).
With 50,000 nodes in a near-linear tree, the repeated walks are quadratic and too slow.
Approach 2 — Single post-order DFS with two states
The two brute-force walks from a node overlap heavily with the walks from its children. Compute each node’s two answers once, bottom-up, from its children’s answers. Define for each node:
down_left = length of the longest zigzag that starts at this node by moving left.down_right = length of the longest zigzag that starts at this node by moving right.
State meaning: think of it as dp[node][dir] with dir ∈ {left, right} — a 2-D DP whose first axis is the node and second axis is the two directions.
Recurrence (a missing child contributes 0):
down_left(node) = 1 + down_right(node.left) # step left, then the child must zig right
down_right(node) = 1 + down_left(node.right) # step right, then the child must zig left
answer = max over all nodes of max(down_left, down_right)
The direction flips across the edge: entering the left child, its contribution is how far it can zigzag starting to the right.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def longestZigZag(root: "TreeNode") -> int:
best = 0
def dfs(node: "TreeNode") -> tuple[int, int]:
# returns (down_left, down_right) for this node
nonlocal best
if not node:
return (-1, -1) # -1 so a leaf edge sums to 0 via 1 + (-1)
l_left, l_right = dfs(node.left)
r_left, r_right = dfs(node.right)
down_left = 1 + l_right # go left, then continue right from child
down_right = 1 + r_left # go right, then continue left from child
best = max(best, down_left, down_right)
return (down_left, down_right)
dfs(root)
return best
Why the -1 sentinel: a None child returns -1, so a node whose left child is missing gets down_left = 1 + (-1) = 0 — the correct “no left edge available.” A leaf therefore returns (0, 0).
Walkthrough on the straight left-left-left chain A → B → C → D (each node’s left child):
D (leaf): returns (0, 0).C has left child D, no right: down_left = 1 + D.down_right = 1 + 0 = 1; down_right = 1 + (-1) = 0. Returns (1, 0).B has left child C: down_left = 1 + C.down_right = 1 + 0 = 1; down_right = 0. Returns (1, 0).A similarly returns (1, 0).
The global max across all nodes is 1 — matching “after one left move you must turn right, and there is no right child.” Correct answer 1.
Complexity: O(n) time (each node visited once, O(1) work), O(h) space for the recursion stack.
Common pitfalls
- Not flipping the direction across the edge — the left child’s rightward run feeds the parent’s leftward path. Using the child’s leftward run instead computes a straight path, not a zigzag.
- Counting nodes instead of edges — length is edges; a leaf is 0. Using node counts yields answers off by one.
- Global vs returned value confusion — the function returns per-node continuation lengths, but the answer is the running maximum updated at every node, not just the root’s value.
- Base case sign — returning
0 (not -1) for None would give a missing child a phantom edge; the -1 sentinel makes 1 + (-1) = 0.
Pattern takeaway
Tree DP generalizes 2-D DP off the grid: the “table” is dp[node][state], computed by a single post-order pass that combines children’s states into the parent’s. Whenever a node’s answer depends on a small set of directional/state variants (here, left-start vs right-start), return a tuple of those states and keep a global best — O(n) beats the O(n^2) recompute-from-each-node brute force.