You are given the root of a binary tree.
A ZigZag path for a binary tree is defined as follow:
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
Return the longest ZigZag path contained in that tree.
Example 1:
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1] Output: 3 Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:
Input: root = [1,1,1,null,1,null,null,1,1,null,1] Output: 4 Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:
Input: root = [1] Output: 0
Constraints:
[1, 5 * 104].1 <= Node.val <= 100Problem Overview: You are given the root of a binary tree and must find the length of the longest ZigZag path. A ZigZag path alternates between left and right child moves at every step. The path can start at any node, and the answer is the maximum number of edges in such an alternating sequence.
Approach 1: Depth-First Search (DFS) Recursive Approach (O(n) time, O(h) space)
This approach uses Depth-First Search to explore every node while tracking the direction of the previous move. For each node, maintain two states: the length of a ZigZag path if the previous move was left and the length if the previous move was right. When moving left, reset the left count and extend the right count, and vice versa. A global variable tracks the maximum length encountered during traversal. Because each node is visited once, the time complexity is O(n), and recursion stack space is O(h), where h is the tree height.
The key insight is that ZigZag paths depend only on the previous direction. By passing the current length and direction during recursion, you avoid recomputing paths from every node. This pattern resembles state transitions commonly seen in Dynamic Programming on trees.
Approach 2: Breadth-First Search (BFS) Iterative Approach (O(n) time, O(n) space)
This method performs a level-order traversal using a queue. Each queue entry stores the current node, the direction of the last move, and the current ZigZag length. When expanding nodes, push children with updated direction and reset the path length when the direction repeats. By iterating through all nodes while tracking direction changes, the algorithm evaluates every possible ZigZag path. The traversal touches each node once, giving O(n) time complexity, while the queue may hold up to O(n) nodes in the worst case.
This iterative version is useful when recursion depth might become large or when you prefer explicit state tracking during traversal. It still relies on standard Binary Tree traversal mechanics.
Recommended for interviews: The DFS recursive approach is typically expected. It demonstrates strong understanding of tree traversal, state propagation, and how to track directional transitions efficiently. Interviewers often look for the insight that two directional states per node are enough to compute the optimal ZigZag path in a single pass.
The recursive DFS approach involves traversing the binary tree starting from each node, keeping track of the length of the path and the direction of the last move. We use recursion to explore all possible ZigZag paths, switching directions (left to right or right to left) at each step and updating the maximum path length observed.
This Python solution defines a recursive function dfs that explores each node of the tree. For each node, it checks both directions and tracks the length of the ZigZag path in each possible direction. A global variable max_len is updated whenever a longer path is found. The initial calls to dfs start with both left and right as the initial directions.
Python
JavaScript
Time Complexity: O(N) where N is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(H) where H is the height of the tree, due to the recursion stack.
The BFS iterative approach involves using a queue to traverse the tree level by level while keeping track of the direction and length of each ZigZag path. At each node, the direction is switched, and we continue exploring all potential ZigZag paths, updating the maximum found path length.
This C++ solution uses a queue to perform a breadth-first search (BFS) on the binary tree. Each queue entry contains a node along with a pair indicating the direction and current length of the ZigZag path. As we explore the tree, we push new nodes into the queue with the opposite direction and updated lengths. maxLen is continually updated with the longest path found.
Time Complexity: O(N) due to a single traversal of all nodes.
Space Complexity: O(N) for storing nodes and their states in the queue.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Recursive Approach | Time Complexity: O(N) where N is the number of nodes in the tree, as each node is visited once. |
| Breadth-First Search (BFS) Iterative Approach | Time Complexity: O(N) due to a single traversal of all nodes. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Recursive with Direction Tracking | O(n) | O(h) | Best general solution. Clean logic and optimal for interviews. |
| BFS Iterative with Queue State | O(n) | O(n) | Useful when avoiding recursion or when explicit traversal state is preferred. |
Longest ZigZag Path in a Binary Tree - | Leetcode-1372 | MICROSOFT | Explanation + Live Code • codestorywithMIK • 12,823 views views
Watch 9 more video solutions →Practice Longest ZigZag Path in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor