What pattern does Longest ZigZag Path in Binary Tree use?

The Pattern: DFS (Stateful Exploration with Direction Tracking) The Heuristic: When a problem requires tracking alternating states along paths in a tree, pass state parameters representing the last move direction and path length, updating them recursively to maintain the alternating constraint and accumulate global results.

Longest ZigZag Path in Binary Tree

Q: What is the time complexity of Longest ZigZag Path in Binary Tree?

O(n). Each node is visited exactly once during the DFS traversal, and constant work is done per node.

Problem

Given the root of a binary tree, return the length of the longest ZigZag path in the tree, where a ZigZag path is defined as a sequence of nodes starting at any node and alternating between left and right child nodes at each step.

The number of nodes in the tree is in the range [1, 5 * 10⁴]
Each node's value is unique or arbitrary (values do not affect the path length calculation)

Example

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]

Output: 3

Starting from the right child of the root, the longest ZigZag path alternates directions: right -> left -> right, with length 3. The algorithm uses a DFS traversal that tracks the length of ZigZag paths ending in left and right directions at each node. At each step, it updates the global maximum length if the current path is longer. The critical moment is when the DFS switches direction and increments the path length, ensuring the alternating pattern is maintained.

Approach

Straightforward Solution

A brute-force approach might try to explore all paths starting at every node, checking if they alternate directions, which would be inefficient and potentially exponential in time.

Core Observation

A ZigZag path alternates direction at each step, so the length of the path ending at a node depends on the length of the path ending at its child in the opposite direction plus one.

Path to Optimal

The key insight is to use DFS to traverse the tree once, passing along the length of the ZigZag path ending in left and right directions. At each node, the longest ZigZag path ending with a left move is one plus the length of the path ending with a right move from its left child, and vice versa. This allows the problem to be solved in a single pass with O(n) time.

Optimal Approach

Use a DFS helper function that, for each node, receives the lengths of ZigZag paths ending with left and right moves. It updates a global maximum length and recursively explores left and right children, swapping and incrementing the path lengths to maintain the alternating pattern. This approach guarantees O(n) time and O(h) space, where h is the tree height.

Time

O(n)

Each node is visited exactly once during the DFS traversal, and constant work is done per node.

Space

O(h)

The recursion stack depth is proportional to the height of the tree, which is O(h). No additional data structures proportional to n are used.

Solution

1class Solution:
2    def longestZigZag(self, root: Optional[TreeNode]) -> int:
3        longest = 0
4
5        def dfs(node, left_length, right_length):
6            nonlocal longest
7
8            if not node:
9                return
10
11            longest = max(longest, left_length, right_length)
12
13            dfs(node.left, right_length + 1, 0)
14            dfs(node.right, 0, left_length + 1)
15
16        dfs(root, 0, 0)
17
18        return longest

Step-by-Step Solution

1

Track and Update Longest ZigZag Path During DFS Traversal

3longest = 0
5def dfs(node, left_length, right_length):
6    nonlocal longest
8    if not node:
9        return
11    longest = max(longest, left_length, right_length)
13    dfs(node.left, right_length + 1, 0)
14    dfs(node.right, 0, left_length + 1)
16dfs(root, 0, 0)
18return longest

Objective

To recursively explore each node, tracking the longest ZigZag paths ending in left and right directions and updating the global maximum length.

Key Insight

Passing two parameters representing the lengths of ZigZag paths ending with left and right moves allows the DFS to maintain the alternating direction constraint naturally. At each node, the algorithm updates the global longest path by comparing it with the current path lengths. The recursive calls swap and increment these lengths to reflect the direction change, enabling a single-pass solution that efficiently accumulates the maximum ZigZag length.

Interview Quick-Check

Core Logic

The DFS maintains two path lengths per node: one for paths ending with a left move and one for paths ending with a right move, updating the global maximum accordingly.

State & Boundaries

The base case returns immediately on null nodes, preventing invalid recursion and ensuring correct path length propagation.

Common Pitfalls & Bugs

Failing to swap and increment the path lengths correctly when recursing leads to incorrect path length calculations and breaks the alternating pattern.

Complexity

The algorithm runs in O(n) time with O(h) space due to DFS traversal and recursion stack.

2

Return the Global Longest ZigZag Path Length

18	`return longest`

Objective

To return the maximum ZigZag path length found after the DFS traversal completes.

Key Insight

The global variable accumulates the longest ZigZag path length during the entire traversal. Returning it at the end provides the final answer without additional computation, leveraging the single-pass DFS's accumulation.

Interview Quick-Check

Core Logic

Returning the global longest variable after DFS completes gives the maximum ZigZag path length in the tree.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 11 Critical

longest = max(longest, left_length, right_length)

Update the global longest ZigZag path length with the maximum of current left and right path lengths.

This line is critical because it records the best ZigZag path found so far, ensuring the final answer reflects the maximum length encountered anywhere in the tree.

Line 13 Critical

dfs(node.left, right_length + 1, 0)

Recursively call DFS on the left child, incrementing the right path length and resetting the left path length.

This call switches direction to left by incrementing the right path length (which ended with a right move) and resetting the left path length, maintaining the alternating pattern.

Line 14 Critical

dfs(node.right, 0, left_length + 1)

Recursively call DFS on the right child, incrementing the left path length and resetting the right path length.

This call switches direction to right by incrementing the left path length (which ended with a left move) and resetting the right path length, preserving the ZigZag alternation.

Line 3 Core

longest = 0

Initialize a variable to track the longest ZigZag path length found so far.

This variable serves as a global accumulator that is updated during DFS traversal to record the maximum ZigZag length encountered, enabling a single-pass solution.

Line 5 Core

def dfs(node, left_length, right_length):

Define the DFS helper function with parameters for the current node and lengths of ZigZag paths ending with left and right moves.

Passing these two lengths allows the function to maintain state about the direction of the last move and the current path length, which is essential for enforcing the alternating direction constraint.

Line 16 Core

dfs(root, 0, 0)

Start the DFS traversal from the root with initial path lengths zero.

This initiates the recursive exploration of the tree, starting with no prior moves, allowing the algorithm to build ZigZag paths from the root downward.

Line 18 Core

return longest

Return the longest ZigZag path length found after traversal.

Returning the global maximum variable provides the final answer, which was accumulated during the DFS traversal.

Line 6 Core

nonlocal longest

Declare that the helper function will modify the outer 'longest' variable.

Using 'nonlocal' allows the recursive function to update the global maximum path length, ensuring that the result is accessible outside the recursion.

Line 8 Core

if not node:

Return immediately if the current node is null.

This base case prevents further recursion on empty branches, ensuring correctness and avoiding errors.

Line 9 Core

return

Return from the function when the node is null to stop recursion.

This line terminates the recursion at leaf nodes, ensuring the DFS does not proceed into invalid nodes.

Test Your Understanding

Why does the DFS function pass and update two separate path lengths for left and right directions at each node?

Because the ZigZag path alternates direction at each step, the longest path ending with a left move depends on the longest path ending with a right move from the child, and vice versa. Tracking both allows the algorithm to correctly extend paths while maintaining the alternating pattern.

Don't just read it. Drill it.

Reconstruct Longest ZigZag Path in Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Longest ZigZag Path in Binary Tree drill

or drill a free problem

1	`class Solution:`
2	`def longestZigZag(self, root: Optional[TreeNode]) -> int:`
3	`longest = 0`
4
5	`def dfs(node, left_length, right_length):`
6	`nonlocal longest`
7
8	`if not node:`
9	`return`
10
11	`longest = max(longest, left_length, right_length)`
12
13	`dfs(node.left, right_length + 1, 0)`
14	`dfs(node.right, 0, left_length + 1)`
15
16	`dfs(root, 0, 0)`
17
18	`return longest`

3	`longest = 0`
5	`def dfs(node, left_length, right_length):`
6	`nonlocal longest`
8	`if not node:`
9	`return`
11	`longest = max(longest, left_length, right_length)`
13	`dfs(node.left, right_length + 1, 0)`
14	`dfs(node.right, 0, left_length + 1)`
16	`dfs(root, 0, 0)`
18	`return longest`