Longest ZigZag Path in a Binary Tree
The key idea
At every node, the best zigzag that turns LEFT here equals one more edge than the best zigzag that turns RIGHT at its left child (and symmetrically for turning right). So a single post-order DFS can return, for each node, the two values (go-left length, go-right length) built from its children, while a global maximum records the best path seen anywhere.
Problem
You are given the root of a binary tree. A ZigZag path is built by choosing any starting node and an initial direction (left or right), moving to the corresponding child, then alternating direction at every step: if you just moved right you must next move left, and if you just moved left you must next move right. You keep moving until there is no child in the required direction. The length of a ZigZag path is the number of edges it uses, which is the number of visited nodes minus 1 (a single node has length 0). Return the length of the longest ZigZag path contained in the tree.
Constraints
- The number of nodes in the tree is in the range
[1, 5 * 10^4]. 1 <= Node.val <= 100
Examples
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Input: root = [1]
Output: 0
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY