Longest ZigZag Path in a Binary Tree - Video Solutions

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.