Longest ZigZag Path in a Binary Tree

Longest ZigZag Path in a Binary Tree

What is this problem about?

The Longest ZigZag Path in a Binary Tree problem asks you to find the longest path in a binary tree that alternates directions at every step. A "ZigZag" means if you just moved Left to reach the current node, your next move MUST be Right, and vice versa. You can start the path at any node in the tree, and you must return the number of edges in the longest such path.

Why is this asked in interviews?

This is a prominent Medium-level tree problem that tests advanced state-tracking during Depth-First Search (DFS). Interviewers ask it to see if a candidate can pass specific contextual information down a recursive call stack. It evaluates your ability to track "where you came from" and make branching decisions based on that history, avoiding unnecessary recalculations.

Algorithmic pattern used

This problem leverages Depth-First Search (DFS) with directed state passing. In your recursive DFS function, you pass the current node, the direction you arrived from (e.g., isLeft), and the current ZigZag length.

• If you arrived from the Left, moving Right increments the length (length + 1), but moving Left breaks the ZigZag, so you must start a brand new sequence of length 1.
• Keep a global maximum variable updated at every step.

Example explanation

Imagine a tree:

    1
     \
      2
     / \
    3   4
     \
      5

Start at root 1.

• Move Right to 2. State: arrived from Left (technically, we just started). Length = 1.
• At node 2, we must move Left to continue ZigZag.
  • Move Left to 3. State: arrived from Right. Length = 1 + 1 = 2.
  • At node 3, we must move Right.
    • Move Right to 5. State: arrived from Left. Length = 2 + 1 = 3. What if we moved Right from node 2 to node 4? We just moved Right to get to 2, so moving Right again breaks the pattern. The sequence resets, starting a new path at node 4 with Length = 1. The maximum ZigZag length is 3 (1 -> 2 -> 3 -> 5).

Common mistakes candidates make

Candidates frequently try to start a brand new DFS traversal from every single node in the tree, resulting in an $O(N^2)$ time complexity that leads to a Time Limit Exceeded error. By passing the running length down the recursive tree, you only need to visit each node exactly once, achieving $O(N)$ optimal time complexity. Another common error is counting the nodes instead of the edges; a path of 3 nodes has 2 edges.

Interview preparation tip

When tackling the Longest ZigZag Path interview pattern, define clear directional flags in your recursive parameters. Using a boolean isLeft or an integer enum (0 for left, 1 for right) clarifies the logic immensely. Whenever a tree problem requires specific movement sequences, always push the history of the "previous step" down into the child function calls.