How do you solve Longest ZigZag Path in a Binary Tree?

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.

Longest ZigZag Path in a Binary Tree

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

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

Q: What pattern does Longest ZigZag Path in a 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.

Medium DFS

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a DFS helper function that, for each node, receives the lengths of ZigZag paths ending with left and right moves…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Pattern Spotlight

DFS (Stateful Exploration with Direction Tracking)

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.

Solution

Python

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

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.

Return the Global Longest ZigZag Path Length

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

1 more step with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Longest ZigZag Path in a 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 a 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`