Longest ZigZag Path in a Binary Tree: DFS Direction Tracking

You are given the root of a binary tree. A zigzag path starts at any node and alternates between going to the left child and the right child (or right then left). The length of a zigzag path is the number of edges in it. Return the longest zigzag path in the tree.

This is LeetCode 1372: Longest ZigZag Path in a Binary Tree, and it is a clean example of DFS with direction tracking. At each node, you need to know how long the current zigzag is if you arrived from the left versus the right. That directional state is what makes this problem different from a plain depth computation.

Why this problem matters

If you have already solved Diameter of Binary Tree, you know the pattern of tracking values across a tree with DFS. Longest ZigZag Path takes that idea and adds a twist: the value you track depends on which direction you came from. You are not just counting depth. You are counting alternating-direction depth, which means each node needs to maintain two separate values.

This direction-sensitive recursion shows up in many tree and graph problems. Once you internalize the idea of carrying "which way did I get here" through the recursion, you unlock a whole class of problems where the answer depends on the path shape, not just the path length.

The problem also reinforces the global max with local return pattern. At every node, you update a global maximum with the best zigzag ending at that node, and you return the left/right zigzag lengths to the parent so it can build on them.

The key insight

At every node, you compute two values:

1. left_len: the length of the longest zigzag path that goes through this node's left child
2. right_len: the length of the longest zigzag path that goes through this node's right child

Here is the critical observation. If you go left to a child, the zigzag must continue by going right from that child. So left_len = 1 + right_len_of_left_child. Similarly, if you go right to a child, the zigzag must continue by going left from that child. So right_len = 1 + left_len_of_right_child.

At each node, you update the global maximum with max(left_len, right_len). Then you let the parent use whichever of these values continues its own zigzag.

This means you do a single post-order DFS, returning a pair (left_len, right_len) from each node. The parent picks the appropriate one based on whether the current node is its left or right child.

The solution

def longestZigZag(root):
    result = 0

    def dfs(node):
        nonlocal result
        if node is None:
            return (-1, -1)
        left_left, left_right = dfs(node.left)
        right_left, right_right = dfs(node.right)
        left_len = 1 + left_right
        right_len = 1 + right_left
        result = max(result, left_len, right_len)
        return (left_len, right_len)

    dfs(root)
    return result

Let's walk through each piece:

• result = 0 initializes the global max. Every node competes to beat this.
• if node is None: return (-1, -1) is the base case. Returning -1 means that when a real node adds 1, a missing child contributes 0 to the zigzag length. This avoids special-casing leaf nodes.
• left_left, left_right = dfs(node.left) gets the zigzag lengths at the left child.
• right_left, right_right = dfs(node.right) gets the zigzag lengths at the right child.
• left_len = 1 + left_right says: "If I go left to my child, the zigzag continues from that child's right zigzag." The +1 is for the edge to the child.
• right_len = 1 + right_left says: "If I go right to my child, the zigzag continues from that child's left zigzag."
• result = max(result, left_len, right_len) updates the global max. The longest zigzag ending at this node is the better of the two directions.
• return (left_len, right_len) gives the parent both values. The parent will pick whichever one matches its direction to this node.

Visual walkthrough

Let's trace the DFS through a small tree step by step. At every node, we compute (left_len, right_len) and update the global max. Watch how the direction alternation builds up the zigzag length from the bottom.

The key moment is Step 4. At node 1, right_len = 1 + left_len_of_child = 1 + 2 = 3. The zigzag path is 1 (right) to 2 (left) to 3 (right) to 4, crossing 3 edges. Each step alternates direction, and the length accumulates through the recursion.

Notice that the zigzag can start at any node, not just the root. The global max check at every node ensures we catch the best one regardless of where it starts.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node we do O(1) work: two additions, a comparison, and a return.

Space is O(h) where h is the height of the tree. That is the recursion stack depth. For a balanced tree, h = log n. For a completely skewed tree, h = n.

The building blocks

This problem is built on three fundamental patterns:

1. Direction-sensitive recursion. At each node, you track separate values for "came from left" and "came from right." This is the same idea behind problems where the path must alternate or follow a specific shape. The skeleton is: return a tuple from each recursive call, and let the parent pick the element that matches its direction.

2. Global max with local return. The recursive function returns (left_len, right_len) to its caller, but also updates a separate global variable with max(left_len, right_len) at each node. This is the same pattern from Diameter of Binary Tree and Binary Tree Maximum Path Sum (LeetCode 124). You return information the parent needs while tracking the answer as a side effect.

3. Null base case with offset. Returning (-1, -1) for null nodes instead of (0, 0) eliminates the need for null checks at every step. The 1 + (-1) = 0 arithmetic handles the "no child" case automatically. This is a useful trick whenever your recursion adds 1 for each edge.

Edge cases to watch for

• Empty tree (root is None): return 0. The DFS immediately returns (-1, -1) and result stays 0.
• Single node: return 0. Both children are null, so left_len = 1 + (-1) = 0 and right_len = 1 + (-1) = 0. The longest zigzag has 0 edges.
• Straight line (all left or all right children): the zigzag length is always 1 at best, because you cannot alternate directions. Every node's zigzag in the non-straight direction is 0.
• Perfect zigzag (alternating left-right all the way down): the zigzag length equals the height of the tree. The recursion accumulates correctly through each alternation.
• Zigzag not starting at the root: the global max check at every node catches this. The longest zigzag might be buried deep in a subtree.

From understanding to recall

You just traced through the recursion and saw how left_len and right_len build up at each node. You understand why going left to a child means you continue from that child's right zigzag, and vice versa. It all makes sense right now.

But in an interview, will you remember to return (-1, -1) for the null case? Will you remember that left_len = 1 + left_right (not 1 + left_left)? The direction swap is the entire trick, and it is easy to mix up under pressure.

Spaced repetition builds recall. You practice writing the solution from scratch at increasing intervals. Each time, you reconstruct the direction swap logic from memory. After a few repetitions, the pattern of "go left, use child's right" becomes automatic.

The direction-sensitive recursion pattern, the global-max-local-return pattern, and the null-base-with-offset pattern are three of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Diameter of Binary Tree - Uses the same global-max-local-return pattern, but without direction tracking. A great warm-up before tackling this problem.
• Longest Univalue Path - Another tree problem where the recursive function returns one value to the parent while tracking a global maximum. The constraint is value matching instead of direction alternation.
• Binary Tree Maximum Path Sum - The hardest variant of global-max-local-return. Same structural skeleton, but with negative values and the max(0, child) twist.