Skip to main content
Talentd

Longest ZigZag Path in a Binary Tree - Solution & Explanation

MediumDynamic ProgrammingTreeDepth-First SearchBinary Tree9 min readAsked at: Amazon, Microsoft
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

C++C#

C++

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(H) where H is the height of the tree, due to the recursion stack.

Breadth-First Search (BFS) Iterative Approach

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Recursive with Direction TrackingO(n)O(h)Best general solution. Clean logic and optimal for interviews.
BFS Iterative with Queue StateO(n)O(n)Useful when avoiding recursion or when explicit traversal state is preferred.

Video Solution

Longest ZigZag Path in a Binary Tree - | Leetcode-1372 | MICROSOFT | Explanation + Live Code • codestorywithMIK • 14,391 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Longest ZigZag Path in a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Zigzag Grid Traversal With Skip