Longest ZigZag Path in a Binary Tree

medium tree dfs

Problem

You are given the root of a binary tree. A ZigZag path for a binary tree is defined as follow: Choose any node in the binary tree and a direction (right or left). If the current direction is right, move to the right child of the current node; otherwise, move to the left child. After each move, change the direction (left becomes right and vice versa). Repeat until you can no longer move (there is no matching child). The ZigZag length is the number of nodes visited minus 1 (that is, the number of edges). Return the longest ZigZag path length in the tree, taken over all starting nodes and directions. In the input notation, _ denotes a null node.

Inputtree = [1, 1, _, _, 1, 1]

Output3

A left-right-left chain of 3 edges (_ denotes a null node).

tree (level-order)

def longest_zigzag(root):
    best = 0
    def dfs(n):
        nonlocal best
        if not n: return (-1, -1)
        ll, lr = dfs(n.left)
        rl, rr = dfs(n.right)
        left, right = lr + 1, rl + 1
        if left > best: best = left
        if right > best: best = right
        return (left, right)
    dfs(root)
    return best

function longestZigzag(root) {
  let best = 0;
  function dfs(n) {
    if (!n) return [-1, -1];
    const [ll, lr] = dfs(n.left);
    const [rl, rr] = dfs(n.right);
    const left = lr + 1, right = rl + 1;
    if (left > best) best = left;
    if (right > best) best = right;
    return [left, right];
  }
  dfs(root);
  return best;
}

class Solution {
    int best;
    public int longestZigzag(TreeNode root) {
        best = 0;
        dfs(root);
        return best;
    }
    private int[] dfs(TreeNode n) {
        if (n == null) return new int[]{ -1, -1 };
        int[] L = dfs(n.left);
        int[] R = dfs(n.right);
        int left = L[1] + 1, right = R[0] + 1;
        if (left > best) best = left;
        if (right > best) best = right;
        return new int[]{ left, right };
    }
}

int best_;
pair<int,int> dfs(TreeNode* n) {
    if (!n) return {-1, -1};
    auto [ll, lr] = dfs(n->left);
    auto [rl, rr] = dfs(n->right);
    int left = lr + 1, right = rl + 1;
    if (left > best_) best_ = left;
    if (right > best_) best_ = right;
    return {left, right};
}
int longestZigzag(TreeNode* root) {
    best_ = 0;
    dfs(root);
    return best_;
}

Explanation

A zigzag path keeps switching direction: go left, then right, then left, and so on. We want the longest such alternating chain anywhere in the tree.

The clever part is what each node reports back during a DFS. Every node returns two numbers: the longest zigzag that continues by going left from it, and the longest that continues by going right.

Here is the alternation magic: to extend the path by stepping left into a child, the child must then continue by going right. So left = lr + 1, where lr is the left child's right-going value. Symmetrically right = rl + 1 uses the right child's left-going value. An empty child returns (-1, -1) so a single node starts at length 0.

Every node updates a global best with its own left and right values, and the final answer is that best.

For example, taking a single step right then left then right builds a chain of length 3, which matches the expected output for the sample tree.

Time: O(n) Space: O(h)