Longest ZigZag Path in a Binary Tree
Medium · Trees · Dynamic Programming · Tree · Depth-First Search · Binary Tree
Problem
A zigzag path in a binary tree starts at any node, moves to its left or right child, and then keeps alternating: after a move to a left child the next move must be to a right child, and the other way round. It ends when the next child it needs is missing (or anywhere earlier).
The length of a zigzag path is its number of moves, so a single node is a path of length 0. Given the root of a binary tree, return the length of the longest zigzag path in it.
Examples
Input: root = [1,null,2,3,4,null,null,5,6,null,7,null,null,null,8] Output: 3
Starting at node 2: right to 4, left to 5, right to 7. The move 1 → 2 cannot join it, since it is also a right move.
Input: root = [1,2,3,null,4,null,null,5,null,null,6] Output: 4
1 → 2 (left) → 4 (right) → 5 (left) → 6 (right).
Input: root = [1] Output: 0
A single node has no moves.
Constraints
- 1 <= number of nodes <= 5 * 10^4
- 1 <= Node.val <= 100
Approaches
- Walk a zigzag from every node — time O(n · h), space O(h)
Follow-up
The same two numbers can be returned upwards instead (post-order), which is how the recursive solution is usually written. The use cases pin the path to the root, and flip the rule to paths that never change direction.
Related problems
Start free on Cariara · Coding problems · System design studio
