Longest ZigZag Path in a Binary Tree

MediumTreestree dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A **zigzag path** starts at any node of a binary tree, picks a direction (left or right), moves to that child, and then keeps moving to a child in the **opposite** direction from the previous move, for as long as that child exists. The length of a zigzag path is the number of edges it traverses (a single node has length 0). Given the root of a non-empty binary tree, return the length of the longest zigzag path anywhere in the tree. Solve it in O(n) by tracking, for each node, the longest zigzag that arrives at it via a left move and via a right move.

Examples

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Starting at the root's right child: right is exhausted, so go left, right, left for 3 edges.
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
From the root go left, right, left, right: 4 edges.
Input: root = [1]
Output: 0
No edges exist.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More tree dp problems