Skip to main content

1372. Longest ZigZag Path in a Binary Tree

medium

Return the length of the longest zigzag path in a binary tree, where a zigzag alternates between left-child and right-child moves. Tree DP with a 2D state per node: best zigzag arriving from the left vs. arriving from the right.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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. Change the direction from right to left or from left to right. Repeat the second and third steps until you can't move in the tree. Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0.) Return the longest ZigZag path contained in that tree.

Constraints

  • The number of nodes in the tree is in the range [1, 5 * 10^4].
  • 1 <= Node.val <= 100

Examples

Example 1

Input
root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output
3

Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2

Input
root = [1,1,1,null,1,null,null,1,1,null,1]
Output
4

Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3

Input
root = [1]
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Per-node 2D DP. For each node return two numbers: longest zigzag ending here going LEFT next, and longest ending here going RIGHT next.

Hint 2

If you arrived at the current node from its parent's left child, your next move must be right — i.e., this node's 'right next' contribution is parent's 'right next' + 1.

Hint 3

At each node, update the global answer with max(leftNext, rightNext).

Hint 4

Iterative or recursive DFS both work; recursion is the cleanest 2-tuple return.

Solution approach

Reveal approach

DFS returning two values per node: leftLen — length of the longest zigzag that ends at this node and whose last edge was a left-child step from the parent; rightLen — same but last edge was a right-child step. Recurrence at parent P with child C reached by a left move from P: C's leftLen = 1 + P-perspective contribution from leftLen of P's left child computed recursively. Cleanest implementation: dfs(node, fromDir) returns the longest zigzag continuing through node when the last move into node was fromDir. From a left arrival, the next move into the left child resets to length 1, while the next move into the right child extends by 1. Track a global max. O(n) time, O(h) space for the recursion stack.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dynamic-programming
  • tree-dp
  • dfs

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Longest ZigZag Path in a Binary Tree and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →