Longest ZigZag Path in a Binary Tree

Longest zigzag path in a binary tree finds the longest path that alternates direction at every step — left, right, left, and so on. The path length is counted in edges, so a single node has length 0. What distinguishes this from ordinary tree recursion is that the answer depends on how a node was reached. A node arrived at from the left can only extend by going right; the same node reached from the right extends by going left. So the recursion carries direction: - At each node, track the current direction and the length of the zigzag arriving there — two separate values, one per direction. Moving in the opposite direction to the one just travelled extends the path by one. Moving in the same direction restarts it at length 1, since the zigzag is broken but a new path begins at that step. That restart is the detail most often missed. Returning 0 on a direction change loses the fresh path starting at the current node, and the answer comes out short on trees where the longest zigzag begins mid-branch. As with Diameter of Binary Tree, the maximum is recorded on the side rather than returned. The recursion must return per-direction lengths so the parent can extend them, while the best answer overall lives in a variable updated at each node. The answer counts edges, not nodes, so a two-node path has length 1. Off-by-one errors here are common and only show on small trees. Every node is visited once with constant work, giving O(n) time and O(h) stack space.

When a path property depends on how you arrived, push that arrival state down as a DFS parameter rather than trying to reconstruct it. Direction-plus-length is the reusable shape — the same technique handles Longest Univalue Path and Binary Tree Maximum Path Sum, which carry different state for the same reason.