Longest ZigZag Path in a Binary Tree

Solving tips

This is tree DP with two states per node: track down_left and down_right (longest zigzag starting by going left vs right), computed bottom-up in one post-order pass.
The direction flips across each edge: down_left(node) = 1 + down_right(node.left) and down_right(node) = 1 + down_left(node.right) — using the child's same-direction run computes a straight path, not a zigzag.
Keep a running global max of max(down_left, down_right) at every node; the answer is not just the root's value. Target O(n) time, O(h) space.
Pitfall: length is EDGES not nodes (a leaf is 0); returning -1 for a null child makes 1+(-1)=0 handle missing children cleanly.

Problem

You are given the root of a binary tree. A zigzag path is defined by:

Start at any node and choose a direction, left or right.
Move to that child, then flip the direction for the next move (left → right → left → …).
Stop whenever you like.

The length of a zigzag path is the number of edges it traverses (a single node with no moves has length 0). Return the length of the longest zigzag path anywhere in the tree.

Examples

Tree [1, null, 1, 1, 1, null, null, 1, 1, null, 1, null, null, null, 1] → 3 — the longest alternating right-left-right-left chain uses 3 edges.
A single node → 0 — no edges to traverse.
A straight left-left-left chain of 4 nodes → 1 — after the first left move you must go right; there is no right child, so the zigzag stops at 1 edge.

Constraints

The number of nodes is in [1, 5 * 10^4].
1 <= Node.val <= 100.

With up to 50,000 nodes, the expected solution is a single O(n) traversal.

Think about it first

Hint 1

For any node, a zigzag that continues *downward through it* is characterized by which direction it leaves the node: "go left, then zigzag" or "go right, then zigzag." Those are two independent quantities to track at every node.

Hint 2

Think bottom-up. If you know, for a node's left child, how long the best "start by going right" zigzag is, then this node's "go left" path is `1 + (that value)` — because after stepping left into the child, the zigzag must turn right. Two states per node — call it a 2-D DP where the second dimension is {left, right}.

Hint 3

Post-order DFS returning `(down_left, down_right)` for each node: `down_left = 1 + down_right(node.left)` and `down_right = 1 + down_left(node.right)` (0 if the child is missing). Update a global maximum with `max(down_left, down_right)` at every node.

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.

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


class Solution:
    def longestZigZag(self, 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).

Why the constraints kill it: 50,000 nodes in a near-linear tree makes the repeated walks quadratic — far too slow.

Approach 2 — Single post-order DFS with two states

The insight: 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


class Solution:
    def longestZigZag(self, root: "TreeNode") -> int:
        self.best = 0

        def dfs(node: "TreeNode") -> tuple[int, int]:
            # returns (down_left, down_right) for this node
            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
            self.best = max(self.best, down_left, down_right)
            return (down_left, down_right)

        dfs(root)
        return self.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.