Longest ZigZag Path in Binary Tree

Problem

A zigzag path alternates between left and right child at each step. Return the length of the longest such path.

Key insight: DFS with direction and current length. If continuing the zigzag, increment; otherwise reset to 1.

Solutions

// C++
int maxLen = 0;
void dfs(TreeNode* node, bool goLeft, int len) {
    if (!node) return;
    maxLen = max(maxLen, len);
    dfs(node->left,  true,  goLeft ? 1 : len + 1);
    dfs(node->right, false, goLeft ? len + 1 : 1);
}
int longestZigZag(TreeNode* root) {
    maxLen = 0;
    dfs(root, true, 0);
    dfs(root, false, 0);
    return maxLen;
}

// Java
int maxLen = 0;
public int longestZigZag(TreeNode root) {
    dfs(root, true, 0);
    dfs(root, false, 0);
    return maxLen;
}
void dfs(TreeNode node, boolean goLeft, int len) {
    if (node == null) return;
    maxLen = Math.max(maxLen, len);
    dfs(node.left,  true,  goLeft ? 1 : len + 1);
    dfs(node.right, false, goLeft ? len + 1 : 1);
}

// JavaScript
function longestZigZag(root) {
    let maxLen = 0;
    function dfs(node, goLeft, len) {
        if (!node) return;
        maxLen = Math.max(maxLen, len);
        dfs(node.left,  true,  goLeft ? 1 : len + 1);
        dfs(node.right, false, goLeft ? len + 1 : 1);
    }
    dfs(root, true, 0);
    dfs(root, false, 0);
    return maxLen;
}

# Python
def longestZigZag(root):
    max_len = [0]
    def dfs(node, go_left, length):
        if not node:
            return
        max_len[0] = max(max_len[0], length)
        dfs(node.left,  True,  1 if go_left else length + 1)
        dfs(node.right, False, length + 1 if go_left else 1)
    dfs(root, True, 0)
    dfs(root, False, 0)
    return max_len[0]

Complexity

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