Longest ZigZag Path in a Binary Tree solution and explanation
9 more videos on this problem
Longest ZigZag Path in a Binary Tree - | Leetcode-1372 | MICROSOFT | Explanation + Live CodecodestorywithMIK · 25:12 · 14K views
Longest ZigZag Path in a Binary Tree - LeetCode 1372 - Python SolutionCode with Carter · 7:03 · 8K views
Longest ZigZag Path in a Binary Tree || Binary Tree || DFS || Leetcode 1372 || C++/Java/PythonAryan Mittal · 13:51 · 7K views
Longest ZigZag Path in a Binary Tree - Python #leetcode #leetcode75Deepti Talesra · 16:06 · 2K views
1372. Longest ZigZag Path in a Binary Tree | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 10:29 · 1K views
Longest ZigZag Path in a Binary Tree - Leetcode 1372 - PythonAlgorithms Casts · 16:01 · 1K views
LeetCode 1372 | Longest ZigZag Path in a Binary Tree | OpHaxor SolutionAlgorithms & Programming Interview Prep · 14:35 · 1K views
Daily Leetcode #1114: Apr 19, 2023 - 1372. Longest ZigZag Path in a Binary TreeProgramming Live with Larry · 14:22 · 1K views
Solving the '1372. Longest ZigZag Path in a Binary Tree' Problem in Java LeetCode 75 Study PlanCoding with Christian · 8:08 · 1K views
1372 Longest ZigZag Path in a Binary TreeReduceComplexity · 13:03 · 740 views
The problem
You are given the root of a binary tree.
A ZigZag path for a binary tree is defined as follow:
- Choose any node in the binary tree and a direction (right or left).
- If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
- Change the direction from right to left or from left to right.
- Repeat the second and third steps until you can't move in the tree.
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:
- The number of nodes in the tree is in the range
[1, 5 * 104]. 1 <= Node.val <= 100
Approach overview
Problem 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.
Approach 1: Depth-First Search (DFS) Recursive Approach
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def longestZigZag(self, root: TreeNode) -> int:
def dfs(node, direction, length):
nonlocal max_len
if not node:
return
max_len = max(max_len, length)
if direction == 0: # left
dfs(node.left, 1, length + 1)
dfs(node.right, 0, 1)
else: # right
dfs(node.left, 1, 1)
dfs(node.right, 0, length + 1)
max_len = 0
dfs(root, 0, 0) # Start direction as left
dfs(root, 1, 0) # Start direction as right
return max_lenfunction TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var longestZigZag = function(root) {
let maxLength = 0;
const dfs = (node, direction, length) => {
if (!node) return;
maxLength = Math.max(maxLength, length);
if (direction === 'left') {
dfs(node.left, 'right', length + 1);
dfs(node.right, 'left', 1);
} else { // direction is 'right'
dfs(node.left, 'right', 1);
dfs(node.right, 'left', length + 1);
}
};
dfs(root, 'left', 0);
dfs(root, 'right', 0);
return maxLength;
};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.
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.
Approach 2: Breadth-First Search (BFS) Iterative Approach
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.
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int longestZigZag(TreeNode* root) {
int maxLen = 0;
queue<pair<TreeNode*, pair<int, int>>> q; // (node, (direction, length))
q.push({root, {0, 0}}); // Start with left
q.push({root, {1, 0}}); // Start with right
while (!q.empty()) {
auto [node, state] = q.front(); q.pop();
int direction = state.first, length = state.second;
maxLen = max(maxLen, length);
if (node->left)
q.push({node->left, {1, direction == 0 ? length + 1 : 1}});
if (node->right)
q.push({node->right, {0, direction == 1 ? length + 1 : 1}});
}
return maxLen;
}
};using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int LongestZigZag(TreeNode root) {
int maxLength = 0;
var queue = new Queue<(TreeNode Node, int Direction, int Length)>();
queue.Enqueue((root, 0, 0));
queue.Enqueue((root, 1, 0));
while (queue.Count > 0) {
var (node, direction, length) = queue.Dequeue();
maxLength = Math.Max(maxLength, length);
if (node.left != null) {
queue.Enqueue((node.left, 1, direction == 0 ? length + 1 : 1));
}
if (node.right != null) {
queue.Enqueue((node.right, 0, direction == 1 ? length + 1 : 1));
}
}
return maxLength;
}
}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 3: Default Approach
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int longestZigZag(TreeNode root) {
dfs(root, 0, 0);
return ans;
}
private void dfs(TreeNode root, int l, int r) {
if (root == null) {
return;
}
ans = Math.max(ans, Math.max(l, r));
dfs(root.left, r + 1, 0);
dfs(root.right, 0, l + 1);
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestZigZag(root *TreeNode) int {
ans := 0
var dfs func(root *TreeNode, l, r int)
dfs = func(root *TreeNode, l, r int) {
if root == nil {
return
}
ans = max(ans, max(l, r))
dfs(root.Left, r+1, 0)
dfs(root.Right, 0, l+1)
}
dfs(root, 0, 0)
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Longest ZigZag Path in a Binary Tree easy or hard?
Longest ZigZag Path in a Binary Tree is considered a Medium difficulty problem. The challenge comes from tracking direction changes during traversal and ensuring paths reset correctly. Once the directional state idea is clear, the implementation becomes straightforward with DFS.
Longest ZigZag Path in a Binary Tree Python/Java solution
Python and Java implementations typically use recursive DFS. Each function call passes the node, the direction of the last move, and the current ZigZag length. The algorithm updates a global maximum and recursively explores both children. The logic remains identical across Python, JavaScript, C++, and C#.
How to solve Longest ZigZag Path in a Binary Tree in O(n)?
Traverse the tree using DFS while tracking the direction of the previous move. When moving left, extend the path if the previous direction was right, otherwise reset the count. Do the same for right moves. Maintain a global maximum during traversal so the entire computation finishes in a single pass through the tree.
What is the best approach for Longest ZigZag Path in a Binary Tree?
The most efficient approach uses Depth-First Search with direction tracking. Each recursive call keeps the current ZigZag length and the direction of the last move. This allows the algorithm to extend the path when the direction alternates and reset when it repeats. The entire tree is processed once, giving O(n) time complexity.
Is Longest ZigZag Path in a Binary Tree asked at Google/Amazon/Meta?
Tree traversal and path problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants that involve alternating paths, longest paths, or dynamic programming on trees are common in mid-level software engineering interviews.
What data structure is used in Longest ZigZag Path in a Binary Tree?
The primary data structure is a binary tree. The solution typically uses Depth-First Search recursion with a few integer variables to track path length and direction. Some implementations also use a queue for Breadth-First Search when solving the problem iteratively.
What is the time complexity of Longest ZigZag Path in a Binary Tree?
The optimal time complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited once while computing ZigZag lengths for left and right transitions. The DFS solution uses O(h) auxiliary space due to recursion, where h is the height of the tree.