1372. Longest ZigZag Path in a Binary Tree

Medium · solved 2026-10-06 · Open on LeetCode

treebinary-treedfsdynamic-programming

Time O(n) · Space O(h)

How to get there

Carry two zigzags down, one per next turn

1. Restate the length. A zigzag path moves down the tree, alternating left and right at every step, and its length counts edges. It can start at any node, in either direction.

2. Try it by hand and find the repeated work. The direct way starts at every node, once going left and once going right, and walks until the alternation breaks. A node deep in a long zigzag is re-walked by every start above it on that zigzag, so the work piles up to O(n · h).

3. Find what a node needs from its parent. A zigzag reaching a node arrived by one move, so its next move is fixed: arriving by a right move, it continues only by going left. So two numbers describe everything that reaches a node: the longest zigzag ending here that would continue by going left, and the one that would continue by going right. In solution.py these are left and right, named for the next move.

4. Derive the child’s numbers from the parent’s. Stepping to the right child is a right move, so it extends the zigzag that wanted a right turn: the child’s left is the parent’s right + 1, and the child’s right is 0, since nothing arrives at a right child by a left move. Stepping left is the mirror image. A brand-new zigzag starting at the parent needs no special case: when the parent’s number is 0, + 1 gives the one-edge path.

5. Take the best anywhere. Every node’s two numbers are lengths of real zigzags, so the answer is the largest number seen at any node.

6. Check the cost. Each node is pushed and popped once: O(n) time. The stack holds pending siblings along one path, O(h).

The reusable recipe: when a path’s next step depends on its last one, carry one running length per possible next step, and let each move extend the one it continues and restart the others.

Let the two lengths' meanings write the pushes

Variable	Always means, for `current`
`left`	the longest zigzag ending at `current` whose next move would be left: it arrived by a right move
`right`	the longest zigzag ending at `current` whose next move would be right: it arrived by a left move
`best`	the longest zigzag seen at any popped node

Code	What happened	What it keeps true
`stack, best = [(root, 0, 0)], 0`	nothing arrives at the root	both lengths start at 0
`best = max(best, left, right)`	both zigzags ending here are complete candidates	`best` covers every popped node
`stack.append((current.right, right+1, 0))`	a right move extends the zigzag that wanted a right turn	at the child, that zigzag now wants a left turn; nothing arrives there by a left move
`stack.append((current.left, 0, left+1))`	a left move extends the zigzag that wanted a left turn	the mirror image

The swap is the part that is easy to misread: going right puts right + 1 into the child’s left slot. Read the names as “the next move”, not “where it came from”, and the swap is exactly the alternation.

The method carries over: name each state by what it allows next, and a transition is then the state it continues, one step longer.

Alternatives compared

Approach	Time	Space	How it works
Walk from every node, both ways	O(n · h)	O(h)	Start a zigzag at each node in each direction and walk until it breaks.
Recursion passing the two lengths	O(n)	O(h)	`visit(node, left, right)` updates the best, then calls itself on each child with the lengths the stack version pushes.
Stack of (node, left, right) (chosen, `solution.py`)	O(n)	O(h)	The same lengths carried on an explicit stack.

The recursion and the stack carry the same two numbers; the stack has no recursion limit. A tree can have 50,000 nodes, and on a perfect zigzag chain that long solution.py returned 49,999 when run locally.

solution.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: TreeNode | None) -> int:
        if not root:
            return 0

        stack, best = [(root, 0, 0)], 0

        while stack:
            current, left, right = stack.pop()

            best = max(best, left, right)

            if current.right:
                stack.append((current.right, right+1, 0))
            if current.left:
                stack.append((current.left, 0, left+1))

        return best

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.