Longest ZigZag Path in a Binary Tree — LC 1372 Deep Dive

Problem Statement

LeetCode 1372 — Longest ZigZag Path in a Binary Tree | Difficulty: Medium

A zigzag path alternates directions: after going left you must go right, and after going right you must go left. Return the length (number of edges) of the longest such path in the tree. A path can start at any node.

Constraints:

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

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
 
Output: 3
Explanation: The longest zigzag goes right → left → right, length = 3.

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
 
Output: 4
Explanation: Longest zigzag path has 4 edges.

Example 3:

Input: root = [1]
 
Output: 0
Explanation: Single node, no edges, length = 0.

Simpler example for tracing:

Input: root = [1,2,3,null,4,null,null,null,5]
 
        1
       / \
      2   3
       \
        4
         \
          5
 
Output: 2
Explanation: 1->2 (left), 2->4 (right), so length = 2. 
Going 4->5 (right again) breaks the zigzag.

Why This Problem Matters

This problem teaches a key DFS design technique: passing direction state down recursive calls. Rather than computing paths bottom-up (which is harder to think about), you pass the current "expected next direction" downward and either extend or reset the streak. The same pattern appears in problems like "longest univalue path", "path with alternating values", and similar streak-tracking questions on sequences and trees. It is a Medium that trips up many candidates because the natural instinct is to try a two-pass or bottom-up approach.

The Core Insight

At every node, you arrive from either the left or the right. If the next move continues the zigzag (the opposite direction from how you arrived), extend the length by 1. If it breaks the zigzag (same direction), reset to 1 (starting a fresh path from this node going the same direction).

Concretely, call dfs(node, goLeft, length):

goLeft = True means we just arrived at this node by going left from its parent, so the zigzag continues if we go right next.
length is the number of edges in the current zigzag path ending at node.

At each node, we always recurse into both children:

Going left: if goLeft is False (we arrived by going right, so continuing left is the zigzag), use length + 1; otherwise reset to 1.
Going right: if goLeft is True (we arrived by going left, so continuing right is the zigzag), use length + 1; otherwise reset to 1.

Track the global maximum across all calls.

Visual Dry Run

dfs(1, goLeft=True, 0) and dfs(1, goLeft=False, 0)

We call dfs from root in both directions to handle paths that start at root going either way.

Call dfs(1, goLeft=False, 0) (arrived at 1 by going right — fictitious):

maxLen = max(0, 0) = 0
Go left (child 2): arriving going left. goLeft=False → continuing left is NOT the zigzag → reset to 1. dfs(2, goLeft=True, 1)
Go right (child 3): goLeft=False → continuing right IS the zigzag → extend. dfs(3, goLeft=False, 1)

dfs(2, goLeft=True, 1):

maxLen = max(0, 1) = 1
Left child of 2 is null → nothing
Right child of 2 is 4: goLeft=True → zigzag goes right → extend. dfs(4, goLeft=False, 2)

dfs(4, goLeft=False, 2):

maxLen = max(1, 2) = 2
Left child null, right child 5: goLeft=False → zigzag goes left, but we're going right → reset to 1. dfs(5, goLeft=False, 1)

dfs(5, goLeft=False, 1):

Leaf node, maxLen = max(2, 1) = 2

Final answer: 2 ✓

Common Mistakes

Resetting to 0 instead of 1 — When the zigzag breaks, the current move itself starts a new path of length 1. Resetting to 0 means you miss counting the current edge.
Only calling dfs once from the root — You need to try starting the path from root going both left and right. A single initial call with a fixed direction misses paths that start going the other way. Alternatively, call with goLeft=True and goLeft=False both, or pass -1 as a "no direction" sentinel.
Using a class-level maxLen variable in Python — Python requires either a list ([0]) or nonlocal to mutate an enclosing variable inside a nested function. Forgetting this causes the global max to never update.
Confusing "length" with "number of nodes" — The problem asks for the number of edges, not nodes. A path with 2 edges visits 3 nodes. Start length at 0 at the root and increment by 1 per edge.
Not recursing into the "wrong" child — Even when a direction breaks the zigzag, you still need to recurse into that child (resetting the count to 1) because a longer zigzag might start from there.
Treating the problem as only allowing paths from root — The zigzag path can start at any node, not just the root. This is why you maintain a global maximum rather than just returning from the root call.

Solutions

# Python — DFS tracking direction and current zigzag length
def longestZigZag(root):
    max_len = [0]   # use a list to allow mutation inside nested function
 
    def dfs(node, go_left, length):
        if not node:
            return
        # Update global maximum with current path length
        max_len[0] = max(max_len[0], length)
 
        if go_left:
            # We arrived going left; zigzag continues by going right
            dfs(node.left,  True,  1)             # going left again: reset to 1
            dfs(node.right, False, length + 1)    # going right: extend zigzag
        else:
            # We arrived going right; zigzag continues by going left
            dfs(node.left,  True,  length + 1)    # going left: extend zigzag
            dfs(node.right, False, 1)              # going right again: reset to 1
 
    # Start from root in both possible directions
    dfs(root, True,  0)   # as if we arrived at root by going left
    dfs(root, False, 0)   # as if we arrived at root by going right
    return max_len[0]

// JavaScript — DFS tracking direction and current zigzag length
function longestZigZag(root) {
    let maxLen = 0;   // global maximum edge count
 
    function dfs(node, goLeft, length) {
        if (!node) return;
 
        // Update the global best
        maxLen = Math.max(maxLen, length);
 
        if (goLeft) {
            // Arrived going left — zigzag continues going right
            dfs(node.left,  true,  1);            // going left again: fresh start
            dfs(node.right, false, length + 1);   // going right: extend
        } else {
            // Arrived going right — zigzag continues going left
            dfs(node.left,  true,  length + 1);   // going left: extend
            dfs(node.right, false, 1);             // going right again: fresh start
        }
    }
 
    // Try both starting directions from the root
    dfs(root, true,  0);
    dfs(root, false, 0);
    return maxLen;
}

Complexity Analysis

Approach	Time	Space
Brute force (try every node as start)	O(n^2)	O(h)
Single DFS with direction state (this solution)	O(n)	O(h)

Every node is visited a constant number of times (twice from the two initial calls, but each sub-call visits each descendant once). The recursion stack is O(h).

Follow-up Questions

What if you want the actual zigzag path, not just the length? Track the best start node and direction during the DFS and reconstruct the path afterwards.
What if the tree is an N-ary tree? The concept extends: at each node, any child that is the "opposite" of how you arrived extends the path; any other child resets. Track the last direction as the index of the child taken.
Can you solve it bottom-up? Yes — each node returns (left_zigzag_length, right_zigzag_length). The parent uses the child's opposite-direction length to extend. The global max is updated at each node.

This Pattern Solves

Streak-tracking problems on trees (longest univalue path, longest alternating path)
Any problem where a path property depends on the direction of arrival at a node
Alternating sequence problems adapted from arrays to trees
Problems where a fresh start must be possible at every node (not just leaves)

Key Takeaways

Pass the current direction (goLeft true/false) as a DFS parameter — this is cleaner than trying to compute zigzag length bottom-up
When the zigzag breaks, reset the length to 1 (not 0) — the current move itself starts a new path
Always recurse into both children even when one resets the count — a longer zigzag might start from the "wrong" child
Call the DFS from the root in both directions to handle paths that start at the root going either way
Track a global maximum updated at every node — the zigzag can start anywhere, not just the root
Time O(n), space O(h) — each node is visited a constant number of times
This direction-tracking DFS pattern applies to any tree problem where path validity depends on arrival direction

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Common Mistakes#

Solutions#

Complexity Analysis#

Follow-up Questions#

This Pattern Solves#

Key Takeaways#

Related reading