hardTreesPure DSA~40 min
Longest Alternating-Direction Path in a Tree
A zigzag path moves down a tree, alternating left and right at each step. Find the length (in edges) of the longest such zigzag path.
Problem
Given the root of a binary tree, a zigzag path starts at any node, picks a direction (left or right), moves to that child, then alternates direction at each subsequent step. Return the length of the longest zigzag path, counted in edges.
Input
A binary tree root.
Output
An integer: the longest zigzag path length in edges.
Constraints
- 1 <= number of nodes <= 5*10^4
- -100 <= node value <= 100
- A single node has zigzag length 0.
Examples
Example 1
Input
root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output
3
The longest alternating path traverses 3 edges.
Example 2
Input
root = [1,1,1,null,1,null,null,1,1,null,1]
Output
4
An alternating chain of 4 edges exists.