LeetCode 1372 - Longest ZigZag Path in a Binary Tree

In this problem, we are given the root node of a binary tree, and we need to find the length of the longest ZigZag path

leetcodemediumdynamic-programmingtreedepth-first-searchbinary-tree

LeetCode Problem 1372

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

In this problem, we are given the root node of a binary tree, and we need to find the length of the longest ZigZag path that exists anywhere inside the tree.

A ZigZag path alternates directions at every step. If we move left from one node, then the next move must go right. If we move right, then the next move must go left. The path can start at any node in the tree, and the initial direction can also be chosen freely.

The length of a ZigZag path is defined as the number of edges traveled, which is equivalent to the number of visited nodes minus one. A single node by itself therefore has a ZigZag length of 0.

The input is a standard binary tree. Each node may have a left child, a right child, both, or neither. The output is a single integer representing the maximum ZigZag length that can be formed anywhere in the tree.

The constraints are important:

  • The tree may contain up to 5 * 10^4 nodes.
  • This means we cannot afford algorithms that repeatedly traverse large portions of the tree.
  • An O(n^2) solution may time out on highly unbalanced trees.
  • We therefore need a solution that processes each node efficiently, ideally once.

Several edge cases are especially important:

  • A tree containing only one node should return 0.
  • A completely skewed tree, where every node only has one child in the same direction, produces a maximum ZigZag length of 1.
  • Alternating left-right chains should correctly accumulate long ZigZag paths.
  • The optimal path does not necessarily start at the root, so the algorithm must consider every node as a potential starting point.

Approaches

Brute Force Approach

The brute-force idea is to treat every node as a potential starting point. For each node, we attempt two traversals:

  • Start by moving left
  • Start by moving right

From there, we recursively continue the ZigZag pattern by alternating directions until the path can no longer continue.

This approach is correct because it explicitly explores every valid ZigZag path in the tree. Since every possible starting node and every initial direction are considered, the longest path will eventually be found.

However, the performance is poor. Suppose the tree is highly unbalanced, similar to a linked list. From each node, we may traverse almost the entire remaining tree. Since there are n starting nodes, this leads to approximately O(n^2) work in the worst case.

With up to 50,000 nodes, this is too slow.

Optimal Depth-First Search Approach

The key observation is that the ZigZag state at a node can be described entirely by:

  • The current node
  • The direction used to arrive at that node
  • The current ZigZag length

This means we can perform a single DFS traversal while carrying the current state forward.

At every node:

  • If we move left, then the next move must be right
  • If we move right, then the next move must be left

We recursively continue the valid ZigZag extension while also restarting new paths from children when necessary.

Because each node is processed only once with constant work, the entire algorithm becomes linear.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(h) Starts a fresh traversal from every node
Optimal DFS O(n) O(h) Single DFS traversal carrying ZigZag state

Here, h represents the height of the tree.

Algorithm Walkthrough

  1. Create a variable called max_length to store the longest ZigZag path discovered so far.
  2. Define a DFS helper function with three parameters:
  • The current node
  • The current ZigZag length
  • The direction of the previous move
  1. If the current node is None, stop recursion immediately because no further path exists.
  2. Update max_length using the current ZigZag length. This ensures that every valid path contributes to the final answer.
  3. If the previous move was to the left, then:
  • Continuing the ZigZag requires moving right
  • Moving right increases the current length by 1
  • Moving left restarts the ZigZag length at 1
  1. Similarly, if the previous move was to the right:
  • Continuing requires moving left
  • Moving left increases the current length by 1
  • Moving right restarts the path at length 1
  1. Start two initial DFS traversals from the root:
  • One assuming the first move goes left
  • One assuming the first move goes right
  1. After DFS completes, return max_length.

Why it works

The algorithm works because every valid ZigZag path is represented during DFS traversal. At each node, the recursion correctly maintains whether the alternating pattern continues or resets. Since every edge is explored exactly once in both directional contexts, the maximum ZigZag length is guaranteed to be discovered.

Python Solution

# 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

from typing import Optional

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        max_length = 0

        def dfs(node: Optional[TreeNode], direction: str, length: int) -> None:
            nonlocal max_length

            if not node:
                return

            max_length = max(max_length, length)

            if direction == "left":
                dfs(node.right, "right", length + 1)
                dfs(node.left, "left", 1)
            else:
                dfs(node.left, "left", length + 1)
                dfs(node.right, "right", 1)

        dfs(root.left, "left", 1)
        dfs(root.right, "right", 1)

        return max_length

The implementation uses a recursive DFS helper function to maintain the current ZigZag state.

The direction parameter represents the direction used to arrive at the current node. This determines which child continues the ZigZag pattern.

When the alternation rule is satisfied, the current length increases by one. When the same direction is repeated, the path effectively restarts from the child node, so the length resets to 1.

The global variable max_length is updated during every DFS call. This ensures that the algorithm tracks the best path encountered anywhere in the tree.

The traversal starts from both root.left and root.right because a ZigZag path must begin with an edge, not a standalone root node.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func longestZigZag(root *TreeNode) int {
    maxLength := 0

    var dfs func(node *TreeNode, direction string, length int)

    dfs = func(node *TreeNode, direction string, length int) {
        if node == nil {
            return
        }

        if length > maxLength {
            maxLength = length
        }

        if direction == "left" {
            dfs(node.Right, "right", length+1)
            dfs(node.Left, "left", 1)
        } else {
            dfs(node.Left, "left", length+1)
            dfs(node.Right, "right", 1)
        }
    }

    if root.Left != nil {
        dfs(root.Left, "left", 1)
    }

    if root.Right != nil {
        dfs(root.Right, "right", 1)
    }

    return maxLength
}

The Go implementation follows the same logic as the Python version but adapts it to Go syntax and semantics.

Go uses nil instead of None, and recursion is implemented using an inner function variable declaration. Since Go does not support nested named functions directly, the DFS helper is declared as a variable before assignment.

The algorithm uses integers safely because the maximum possible ZigZag length is bounded by the number of nodes, which is far below Go's integer limits.

Worked Examples

Example 1

Input:

[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]

The longest ZigZag path is:

right -> left -> right

Length = 3

Traversal progression:

Current Node Previous Direction Current Length Max Length
root.right right 1 1
left child left 2 2
right child right 3 3

The traversal eventually terminates because no further alternating move exists.

Final answer:

3

Example 2

Input:

[1,1,1,null,1,null,null,1,1,null,1]

Longest path:

left -> right -> left -> right

Traversal table:

Current Node Previous Direction Current Length Max Length
root.left left 1 1
right child right 2 2
left child left 3 3
right child right 4 4

Final answer:

4

Example 3

Input:

[1]

The tree contains only one node.

No edges exist, so no ZigZag movement is possible.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited a constant number of times
Space O(h) Recursive call stack depends on tree height

The DFS traversal processes each node once for each directional context, but this still results in linear total work. The recursion depth depends on the height of the tree. In the worst case of a skewed tree, the height becomes O(n).

Test Cases

# Definition for testing
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):
        max_length = 0

        def dfs(node, direction, length):
            nonlocal max_length

            if not node:
                return

            max_length = max(max_length, length)

            if direction == "left":
                dfs(node.right, "right", length + 1)
                dfs(node.left, "left", 1)
            else:
                dfs(node.left, "left", length + 1)
                dfs(node.right, "right", 1)

        if root.left:
            dfs(root.left, "left", 1)

        if root.right:
            dfs(root.right, "right", 1)

        return max_length

solution = Solution()

# Single node tree
root = TreeNode(1)
assert solution.longestZigZag(root) == 0  # No edges

# Simple alternating chain
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
root.right.left.right = TreeNode(4)
assert solution.longestZigZag(root) == 3  # Perfect ZigZag chain

# Straight left chain
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)
root.left.left.left = TreeNode(4)
assert solution.longestZigZag(root) == 1  # Cannot alternate directions

# Straight right chain
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
assert solution.longestZigZag(root) == 1  # Only one valid move

# Balanced tree with multiple ZigZag paths
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(5)
assert solution.longestZigZag(root) == 3  # left -> right -> left

# Optimal path not starting at root
root = TreeNode(1)
root.left = TreeNode(2)
root.left.right = TreeNode(3)
root.left.right.left = TreeNode(4)
root.left.right.left.right = TreeNode(5)
assert solution.longestZigZag(root) == 4  # Deep subtree path

# Tree with both children but no long ZigZag
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
assert solution.longestZigZag(root) == 1  # Single edge only
Test Why
Single node tree Verifies minimum boundary condition
Alternating chain Tests ideal ZigZag continuation
Straight left chain Ensures reset logic works
Straight right chain Verifies symmetry
Balanced tree Tests multiple candidate paths
Deep subtree path Confirms optimal path may not start at root
Small two-child tree Validates simple non-alternating structure

Edge Cases

A single-node tree is the smallest valid input. Since there are no edges, the ZigZag length must be 0. Implementations that incorrectly count nodes instead of edges may mistakenly return 1. This solution avoids that issue because the DFS only begins after traversing an edge.

A completely skewed tree is another important edge case. For example, if every node only has a left child, then alternating directions becomes impossible after one move. A naive implementation might continue counting consecutive left moves incorrectly. This algorithm handles the situation correctly by resetting the path length whenever the same direction repeats.

Another tricky case occurs when the longest ZigZag path does not begin at the root. Some incorrect solutions only explore paths starting from the root node, which misses optimal paths deeper in the tree. This implementation naturally handles all possible starting positions because every recursive call can restart the ZigZag count from its child nodes.

A highly unbalanced tree with up to 50,000 nodes is also significant. Recursive solutions risk deep recursion stacks. The algorithm still satisfies the required asymptotic complexity, processing each node only once while maintaining linear runtime.