Longest ZigZag Path in a Binary Tree

Problem in plain words

A zigzag path starts at any node, takes one step to a child (left or right), and then must keep alternating direction: left, right, left, … or right, left, right, …. Its length is the number of steps (edges). Return the length of the longest zigzag path anywhere in the tree. A single node has length 0.

Example: root A has a right child B, B has a left child C, and C has a right child D. The path A → B → C → D goes right, left, right, so its length is 3.

Intuition

For each node, remember two numbers: l, the length of the longest zigzag that ends here having just stepped left into this node, and r, the same for a step right into it. If you go to the left child, you are stepping left, so the zigzag can continue only if the previous step was right: the child's l becomes r + 1, and its r resets to 0 (a fresh path could start by going right from it). Symmetrically, the right child gets r = l + 1 and l = 0. The answer is the largest value seen.

Approach

1. Start at the root with l = 0 and r = 0.
2. At each node, update best = max(best, l, r).
3. Visit the left child with (r + 1, 0).
4. Visit the right child with (0, l + 1).
5. Return best after the whole tree is explored.

Dry run

Java solution

class Solution {
    private int best = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root, 0, 0);
        return best;
    }

    // left  = zigzag length ending here with a step to the left
    // right = zigzag length ending here with a step to the right
    private void dfs(TreeNode node, int left, int right) {
        if (node == null) {
            return;
        }
        best = Math.max(best, Math.max(left, right));
        dfs(node.left, right + 1, 0);
        dfs(node.right, 0, left + 1);
    }
}

Python solution

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        best = 0
        stack = [(root, 0, 0)]
        while stack:
            node, left_len, right_len = stack.pop()
            best = max(best, left_len, right_len)
            if node.left:
                stack.append((node.left, right_len + 1, 0))
            if node.right:
                stack.append((node.right, 0, left_len + 1))
        return best

Complexity

Edge cases and common mistakes

• Counting nodes instead of edges — the length is the number of steps, so a lone node is 0.
• Mixing up the two slots — stepping left continues a path whose last step was right, so the left child gets r + 1, not l + 1. The other slot becomes 0, meaning a new zigzag can start at the child.
• Starting a fresh DFS from every node — that is O(n²). The two-length state lets every node be handled once.
• Recursion depth in Python — with up to 5·10^4 nodes, a skewed tree can exceed the default recursion limit; the iterative stack avoids that.