Longest ZigZag Path LeetCode 1372 Guide

LeetCode 1372 — Longest ZigZag Path in a Binary Tree — gives you the root of a binary tree and asks you to find the length of the longest zigzag path. A zigzag path alternates directions at every step: left then right then left, or right then left then right. The length is measured in edges, not nodes.

A zigzag path can start from any node in the tree — not just the root. This means you cannot simply run a DFS from the root and always try to extend; you must handle restarts from any node. The answer is the maximum number of edges in any such alternating-direction path.

With up to 5×10⁴ nodes, an O(n²) brute force restarting DFS from every node would be too slow. The key insight is that a single DFS can track every possible zigzag path simultaneously by carrying two counters at each node: one for paths arriving from the left, one for paths arriving from the right.

The core idea is to pass two values down to every node: leftLen (the zigzag length if you continue by going left from this node) and rightLen (the zigzag length if you continue by going right). At the root, both start at 0 because no edges have been traversed yet.

When visiting a node's left child, the zigzag extends if we came from the right — so we pass rightLen+1 as the new leftLen and 0 as the new rightLen (starting fresh for the right direction). Symmetrically, when visiting a node's right child, we pass 0 as the new leftLen and leftLen+1 as the new rightLen.

At each node, the current zigzag length from both directions is max(leftLen, rightLen). We update a global maximum with this value at every node visit. This single traversal covers all starting points because whenever a counter resets to 0 at some node, the subsequent increments build up a new zigzag starting from that node.

The algorithm uses a recursive DFS with a global maximum variable. The function signature is dfs(node, leftLen, rightLen) where leftLen is how long the zigzag is if we arrived going left to reach this node, and rightLen is how long if we arrived going right.

At each node we update the global max and recurse into both children with correctly swapped and reset counters. The left child receives rightLen+1 as its leftLen (continuing the zigzag from the right) and 0 as its rightLen (reset). The right child receives 0 as its leftLen (reset) and leftLen+1 as its rightLen (continuing the zigzag from the left).

The function initializes with dfs(root, 0, 0). After the traversal completes, the global maximum holds the answer. The algorithm visits every node exactly once, giving O(n) time and O(h) space for the call stack where h is the tree height.

Each node can be part of a zigzag arriving from the left or a zigzag arriving from the right. These are distinct paths that may have very different lengths. Tracking both simultaneously allows each child to pick up whichever direction continues the zigzag and correctly reset the counter for the direction that breaks the zigzag.

A single counter approach would lose information: if you only track length without direction, when you visit the left child you do not know whether the current streak was built going left (same direction — streak breaks) or going right (opposite direction — streak continues). The two-counter design makes direction explicit without any conditional checks.

The reset to 0 passed to the same-direction child is the key: it means that child starts building a new zigzag from scratch, but going the opposite way from there. So every node is simultaneously the potential start of a fresh zigzag in both directions, and the two counters capture exactly this.

Consider the tree [1, null, 1, 1, 1, null, null, 1, 1, null, 1]. The root has only a right child. That right child has both left and right children. The target zigzag goes root→right→left→right→left = 4 edges.

At the root: dfs(root, 0, 0) — ans = 0. We go right: dfs(rightChild, 0, 1). At rightChild: ans = max(0, 0, 1) = 1. We go left: dfs(leftGrandchild, 2, 0); we go right: dfs(rightGrandchild, 0, 1). At leftGrandchild: ans = max(1, 2, 0) = 2. Continue going right from it: dfs(its right child, 0, 3). At that node: ans = max(2, 0, 3) = 3. Go left from it: dfs(deepest left, 4, 0). At deepest left: ans = max(3, 4, 0) = 4.

The final answer is 4 edges. Each step along the right→left→right→left chain incremented the correct counter by 1 and reset the other to 0, cleanly tracking the alternating path without any backtracking or restart.

In Python, use a nonlocal ans variable inside a nested dfs function. dfs(node, left, right): if not node, return; nonlocal ans; ans = max(ans, left, right); dfs(node.left, right+1, 0); dfs(node.right, 0, left+1). Call dfs(root, 0, 0) and return ans. The function is about 8 lines and runs in O(n) time with O(h) call-stack space.

In Java, store ans as an instance variable or a one-element int array. The recursive method void dfs(TreeNode node, int left, int right) updates ans = Math.max(ans, Math.max(left, right)) then calls dfs(node.left, right+1, 0) and dfs(node.right, 0, left+1). The longestZigZag method initializes ans and calls dfs(root, 0, 0). Both implementations are essentially identical in structure.

Time complexity is O(n) — every node is visited exactly once. Space complexity is O(h) for the recursion stack, where h is the height of the tree. For a balanced tree h = O(log n); for a skewed tree (all nodes going one direction) h = O(n). The reset-to-0 passed for the same-direction child is the single most important line in the solution.

Diameter of Binary Tree (LeetCode 543) uses a similar post-order pattern: each node returns the max depth of its subtree, and the diameter at that node is left depth + right depth. Like zigzag, the answer is updated at every node, not just at the root. Both problems require tracking a global maximum that may be achieved at any internal node.

Binary Tree Maximum Path Sum (LeetCode 124) is the weighted generalization: instead of counting edges, you sum node values along the path. The split between going through the current node versus propagating one branch upward mirrors the zigzag logic of continuing versus resetting. Path Sum (LeetCode 112) and Path Sum II (LeetCode 113) are simpler root-to-leaf variants of the same family.

The tree path tracking family — diameter, max path sum, zigzag path, LCA of deepest leaves — all share the post-order DFS skeleton where each node computes a local answer using information from both subtrees and propagates a single value (depth, max gain, zigzag length) upward to its parent. Mastering one makes the others significantly easier to recognize and implement.