#1372

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Longest ZigZag Path in a Binary Tree

Find the longest ZigZag path in a binary tree using depth-first search and dynamic programming for precise node state tracking.

dynamic programming tree depth first search binary tree

Problem Statement

Given the root of a binary tree, compute the longest ZigZag path, defined as a sequence of nodes where each step alternates between left and right child nodes. The length of a ZigZag path is the number of nodes visited minus one, meaning a single node has a length of zero.

Your task is to implement an efficient algorithm that explores all possible paths, tracks the direction at each node, and returns the maximum ZigZag length. Consider that the tree can contain up to 5 * 10^4 nodes, and each node value is between 1 and 100.

Examples

Example 1

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]

Output: 3

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

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

Example 3

Input: root = [1]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Depth-First Search with Direction Tracking

Use a DFS function that takes the current node and the previous direction (left or right). For each node, recursively explore both children, flipping the direction and updating the current ZigZag length.

Dynamic Programming for Subtree States

Store the maximum ZigZag length starting from each node in both left and right directions. This avoids recomputing the same subpaths and ensures O(n) complexity for all nodes.

Updating Global Maximum

Maintain a global variable to track the overall maximum ZigZag length found. At each recursive call, compare the current path length with this global maximum and update accordingly.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The algorithm visits each node once with DFS, giving O(n) time complexity. Storing maximum lengths per node in both directions requires O(n) space in the recursion stack and memoization structures.

What Interviewers Usually Probe

Are you correctly flipping direction at each step?
Have you considered updating a global maximum instead of returning only local values?
Can your DFS handle the largest trees efficiently without recomputation?

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract one from node count to get ZigZag length.
Only tracking one direction from root instead of both left and right.
Not updating the global maximum at every node, missing longer subpaths.

Follow-up variants

Compute longest ZigZag path starting specifically from leaf nodes only.
Return the actual sequence of node values forming the longest ZigZag.
Count ZigZag paths that exceed a given minimum length instead of maximum.

FAQ

What is a ZigZag path in a binary tree?

A ZigZag path alternates between left and right child nodes at each step, and its length is the number of nodes visited minus one.

How do I implement maxZigZag(node, direction)?

Use recursion with DFS, passing the current node and last direction, then flip direction for child calls and track the length.

Why do we need both left and right states per node?

Each node can start a ZigZag path in either direction, so tracking both ensures we capture the maximum path from every subtree.

What is the time complexity for Longest ZigZag Path in a Binary Tree?

Visiting each node once with DFS and tracking both directions results in O(n) time complexity.

Can GhostInterview provide step-by-step tracing?

Yes, it offers detailed recursive path tracing and state updates to verify why each node contributes to the maximum ZigZag length.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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) -> int:
        def dfs(root, l, r):
            if root is None:
                return
            nonlocal ans
            ans = max(ans, l, r)
            dfs(root.left, r + 1, 0)
            dfs(root.right, 0, l + 1)

        ans = 0
        dfs(root, 0, 0)
        return ans

Continue Practicing

#1373 maximum sum bst in binary tree #968 binary tree cameras #1367 linked list in binary tree