Problem statement

You are given the root of a binary tree. A zigzag path starts at any node, first moves to its left or right child, and from then on alternates direction at every step (left, right, left, … or right, left, right, …), stopping whenever the next node in that direction does not exist.

The length of a zigzag path is the number of edges it uses (a single node has length 0). Return the length of the longest zigzag path in the tree.

Example 1

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Explanation: Starting at the root's right child, the path right → left → right covers 3 edges.

Example 2

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: From the root: left → right → left → right, 4 edges.

Example 3

Input: root = [1]
Output: 0
Explanation: A single node has a zigzag path of length 0.

Constraints

• 1 <= number of nodes <= 5 · 10^4
• 1 <= Node.val <= 100

Hints for Longest ZigZag Path in a Binary Tree

1. Hint 1

   For each node, the only thing that matters about the path arriving at it is its length and the direction of its last step.

2. Hint 2

   Keep two numbers per node: the longest zigzag ending here whose last move was to the left, and the one whose last move was to the right.

3. Hint 3

   Moving to the left child extends the path that last moved right (right + 1) and resets the other to 0; moving to the right child does the mirror. Take the maximum over all nodes.

How to solve Longest ZigZag Path in a Binary Tree

A zigzag path ending at a node is determined by its last move. Passing down two lengths — the longest path arriving by a left move and by a right move — lets every node extend the right one in O(1).

Approach

1. Call walk(root, left = 0, right = 0), where left is the longest zigzag ending at this node whose last move went left, and right likewise.
2. Record max(left, right) in the answer.
3. For the left child, call walk(child, right + 1, 0): arriving by a left move continues a path whose previous move was right, or starts a new one (length 1 at least, since right + 1 >= 1).
4. For the right child, call walk(child, 0, left + 1).

Why it works

A zigzag path ending at a left child either is the single edge from its parent or extends a path that reached the parent by a right move — exactly right + 1. The 0 passed for the other direction is correct because a path cannot reach a left child by a right move. Every path ends somewhere, so the maximum over nodes covers them all.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• Counting nodes instead of edges is off by one.
• A path may start anywhere, not only at the root — resetting to 1 on a same-direction step handles that.

Reference solution

Python

from typing import Optional

def longestZigZag(root: Optional[TreeNode]) -> int:
    def walk(node, left, right):
        best = max(left, right)
        if node.left:
            best = max(best, walk(node.left, right + 1, 0))
        if node.right:
            best = max(best, walk(node.right, 0, left + 1))
        return best

    return walk(root, 0, 0)

Java

public static int longestZigZag(TreeNode root) {
    return zigWalk(root, 0, 0);
}

static int zigWalk(TreeNode node, int left, int right) {
    int best = Math.max(left, right);
    if (node.left != null) best = Math.max(best, zigWalk(node.left, right + 1, 0));
    if (node.right != null) best = Math.max(best, zigWalk(node.right, 0, left + 1));
    return best;
}

C++

int zigWalk(TreeNode* node, int left, int right);

int longestZigZag(TreeNode* root) {
    return zigWalk(root, 0, 0);
}

int zigWalk(TreeNode* node, int left, int right) {
    int best = max(left, right);
    if (node->left) best = max(best, zigWalk(node->left, right + 1, 0));
    if (node->right) best = max(best, zigWalk(node->right, 0, left + 1));
    return best;
}

JavaScript

var longestZigZag = function(root) {
    return zigWalk(root, 0, 0);
};

var zigWalk = function(node, left, right) {
    var best = Math.max(left, right);
    if (node.left !== null) best = Math.max(best, zigWalk(node.left, right + 1, 0));
    if (node.right !== null) best = Math.max(best, zigWalk(node.right, 0, left + 1));
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium