Problem Description

You have a binary tree and need to find the longest zigzag path within it.

A zigzag path follows these rules:

• Start at any node in the tree and pick an initial direction (left or right)
• Move to the corresponding child node based on your current direction
• After each move, switch directions (if you went left, next go right; if you went right, next go left)
• Continue alternating directions until you can't move further

The length of a zigzag path is calculated as the number of nodes visited minus 1. This means:

• A single node has a zigzag length of 0
• A path through 2 nodes has a zigzag length of 1
• A path through 3 nodes has a zigzag length of 2, and so on

Your task is to return the length of the longest possible zigzag path that can be found anywhere in the given binary tree.

For example, if you have a path that goes: node → left child → right child → left child, this would visit 4 nodes, giving a zigzag length of 3.

The solution uses a depth-first search (DFS) approach where dfs(root, l, r) tracks:

• l: the length of the zigzag path coming into the current node from a left move
• r: the length of the zigzag path coming into the current node from a right move

At each node, the function:

1. Updates the maximum zigzag length seen so far
2. Recursively explores the left child (extending the right-zigzag path and resetting the left)
3. Recursively explores the right child (extending the left-zigzag path and resetting the right)

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart leads us directly to using Depth-First Search.

Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach for this problem.

This makes sense because:

1. We need to explore all possible zigzag paths starting from any node in the tree
2. At each node, we need to track the zigzag path length coming from different directions (left or right)
3. DFS allows us to recursively traverse the tree while maintaining state about the current zigzag path
4. We can efficiently compute the maximum zigzag length by exploring each subtree and tracking the best path found so far

The DFS pattern is ideal here as it naturally follows the tree structure and allows us to build up zigzag paths incrementally as we traverse from parent to child nodes.

Intuition

The key insight is that at any node in the tree, we can arrive from two possible directions - either from a left move or a right move from the parent. This arrival direction determines what our next move must be to continue the zigzag pattern.

Think of it this way: if we just moved left to reach the current node, our next move (if we continue) must be to the right. Similarly, if we arrived by moving right, we must go left next. This alternating pattern is the essence of zigzag.

At each node, we need to track two pieces of information:

1. The length of the zigzag path if we arrived here by going left (from parent's perspective)
2. The length of the zigzag path if we arrived here by going right (from parent's perspective)

Why two values? Because depending on how we arrived at a node, we have different continuation options:

• If we came from a left move (parent went left to reach us), we can only continue the zigzag by going right
• If we came from a right move (parent went right to reach us), we can only continue the zigzag by going left

When we visit a node's left child, we're making a left move. This means:

• The zigzag path that was coming from the right (r) can continue, so we pass r + 1
• Any zigzag path coming from the left cannot continue (it would require two consecutive left moves), so we reset it to 0

Similarly, when visiting the right child:

• The zigzag path coming from the left (l) can continue, so we pass l + 1
• The path from the right resets to 0

Starting from the root with dfs(root, 0, 0) makes sense because the root has no parent, so there's no existing zigzag path coming into it from either direction.

As we traverse the tree, we continuously update our answer with the maximum of the current answer and the two path lengths at each node, ensuring we capture the longest zigzag path anywhere in the tree.

Learn more about Tree, Depth-First Search, Dynamic Programming and Binary Tree patterns.

Solution Approach

The solution implements a DFS traversal with state tracking at each node. Here's how the implementation works:

Core DFS Function: The function dfs(root, l, r) takes three parameters:

• root: the current node being visited
• l: length of the zigzag path arriving from a left move
• r: length of the zigzag path arriving from a right move

Base Case: If the current node is None, we simply return without doing anything - this handles leaf nodes' null children.

Update Maximum: At each node, we update the global answer with ans = max(ans, l, r). This captures the longest zigzag path that passes through the current node, comparing:

• The current maximum answer
• The zigzag length if we arrived from the left (l)
• The zigzag length if we arrived from the right (r)

Recursive Calls: The key insight is in how we make recursive calls to children:

1. Left child traversal: dfs(root.left, r + 1, 0)

   • We're moving left from the current node
   • If we had a zigzag path coming from the right (r), it can continue, so we pass r + 1
   • Any path coming from the left cannot continue (would break zigzag), so we pass 0

2. Right child traversal: dfs(root.right, 0, l + 1)

   • We're moving right from the current node
   • If we had a zigzag path coming from the left (l), it can continue, so we pass l + 1
   • Any path coming from the right cannot continue, so we pass 0

Initialization:

• We use a nonlocal ans variable to track the maximum zigzag length found
• Start the traversal with dfs(root, 0, 0) since the root has no parent (no existing zigzag path)
• Return the final answer

Why This Works: The algorithm ensures that at every node, we consider all possible zigzag paths passing through it. By maintaining separate counters for paths arriving from different directions and properly updating them based on the zigzag rules, we guarantee finding the maximum length zigzag path in the entire tree.

The time complexity is O(n) where n is the number of nodes, as we visit each node exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this binary tree:

        1
       / \
      2   3
     /     \
    4       5
   /
  6

We'll trace through the DFS calls to see how the algorithm finds the longest zigzag path.

Initial Call: dfs(node 1, 0, 0)

• At root node 1, ans = max(0, 0, 0) = 0
• Call dfs(node 2, 0+1, 0) for left child
• Call dfs(node 3, 0, 0+1) for right child

Processing Node 2: dfs(node 2, 1, 0)

• We arrived here by going left (l=1, r=0)
• Update ans = max(0, 1, 0) = 1
• Call dfs(node 4, 0+1, 0) for left child
• Node 2 has no right child

Processing Node 4: dfs(node 4, 1, 0)

• We arrived by going left again (l=1, r=0)
• Update ans = max(1, 1, 0) = 1
• Call dfs(node 6, 0+1, 0) for left child
• Node 4 has no right child

Processing Node 6: dfs(node 6, 1, 0)

• Leaf node, arrived by going left (l=1, r=0)
• Update ans = max(1, 1, 0) = 1
• Both children are null, return

Back to Node 3: dfs(node 3, 0, 1)

• We arrived by going right from node 1 (l=0, r=1)
• Update ans = max(1, 0, 1) = 1
• Node 3 has no left child
• Call dfs(node 5, 0, 0+1) for right child

Processing Node 5: dfs(node 5, 0, 1)

• We arrived by going right (l=0, r=1)
• Update ans = max(1, 0, 1) = 1
• Both children are null, return

The maximum zigzag length found is 1, which corresponds to any two-node path (like 1→2, 1→3, 2→4, etc.).

Now let's modify the tree to see a longer zigzag:

        1
       /
      2
       \
        3
       /
      4

Trace for the zigzag path:

• dfs(node 1, 0, 0): Start at root
• dfs(node 2, 1, 0): Went left to node 2, so r=1 for continuing zigzag
• dfs(node 3, 0, 2): Went right to node 3, previous r becomes l+1 = 0+1 = 2
• dfs(node 4, 3, 0): Went left to node 4, previous l becomes r+1 = 2+1 = 3
• At node 4: ans = max(previous, 3, 0) = 3

The zigzag path 1→2→3→4 visits 4 nodes, giving a length of 3 (nodes - 1). The algorithm correctly identifies this by tracking how the zigzag length grows as we alternate directions: left (0→1), right (1→2), left (2→3).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree. The algorithm performs a depth-first search (DFS) traversal of the tree, visiting each node exactly once. At each node, it performs constant time operations (updating the maximum value and making recursive calls), so the overall time complexity is linear with respect to the number of nodes.

Space Complexity: O(h) where h is the height of the binary tree. The space complexity is determined by the recursive call stack. In the worst case of a skewed tree (essentially a linked list), the height h equals n, making the space complexity O(n). In the best case of a perfectly balanced tree, the height is log(n), making the space complexity O(log n). The algorithm uses a constant amount of extra space for variables (ans, l, r) apart from the recursion stack.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Swapping the Parameters in Recursive Calls

One of the most common mistakes is mixing up which parameter to increment and which to reset when making recursive calls. Many developers incorrectly write:

Incorrect Implementation:

# WRONG: Parameters are swapped
dfs(node.left, left_length + 1, 0)  # Should be right_length + 1
dfs(node.right, 0, right_length + 1)  # Should be left_length + 1

Why This Fails: The zigzag pattern requires alternating directions. When you move left from a node, you can only continue a zigzag path that arrived from the right (and vice versa). Using the wrong parameter breaks this alternation logic.

Correct Implementation:

# When moving left, continue the path that came from right
dfs(node.left, right_length + 1, 0)
# When moving right, continue the path that came from left  
dfs(node.right, 0, left_length + 1)

2. Forgetting to Initialize Both Directions to 0 at the Root

Another pitfall is starting with non-zero values for the initial DFS call:

Incorrect:

dfs(root, 1, 1)  # WRONG: Assumes the root already has path length 1

Why This Fails: The root node has no parent, so there's no existing zigzag path coming into it. Starting with non-zero values would incorrectly count the root as part of a non-existent parent path.

Correct:

dfs(root, 0, 0)  # Start with no existing path from either direction

3. Not Using Nonlocal for the Answer Variable

Forgetting to declare the answer variable as nonlocal leads to scope issues:

Incorrect:

def longestZigZag(self, root: TreeNode) -> int:
    def dfs(node, left_length, right_length):
        if node is None:
            return
        max_length = max(max_length, left_length, right_length)  # ERROR: UnboundLocalError
        # ...
  
    max_length = 0
    dfs(root, 0, 0)
    return max_length

Correct:

def dfs(node, left_length, right_length):
    if node is None:
        return
    nonlocal max_length  # Properly declare access to outer scope variable
    max_length = max(max_length, left_length, right_length)

4. Misunderstanding the Path Length Calculation

Some developers mistakenly think the path length equals the number of nodes visited:

Incorrect Understanding:

• Path through 3 nodes = length 3 ❌

Correct Understanding:

• Path through 3 nodes = length 2 (number of edges) ✓
• The algorithm handles this by incrementing the count when moving to children

The solution correctly handles this by passing length + 1 to children, effectively counting edges rather than nodes.