Longest ZigZag Path in a Binary Tree – LeetCode75 Python Solution Explained

The Longest ZigZag Path in a Binary Tree problem (LeetCode75) is an advanced binary tree challenge that evaluates your understanding of DFS traversal, recursion and path tracking. It is a popular interview question for testing tree traversal strategies and problem-solving skills in scenarios with directional constraints.

In this blog, we will break down the problem, provide a Python solution with detailed code explanations, analyze complexity and discuss real-world applications.

Problem Statement

A ZigZag path in a binary tree is defined as:

• Starting at any node, move to a child node in alternating directions.
• Example: left → right → left → right, etc.

You are tasked to find the length of the longest ZigZag path in a given binary tree.

Example 1

Input:

root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]

Output:

4

Explanation:
The longest ZigZag path follows the pattern right → left → right → left.

Example 2

Input:

root = [1,1,1,null,1,null,null,1,1,null,1]

Output:

3

Understanding the Problem

Key points:

• A ZigZag path alternates between left and right child nodes.
• The path does not need to start at the root, but can start at any node.
• Recursive DFS traversal is ideal to track the length of ZigZag paths.
• Use a variable to store the maximum path length found so far.

Complete Python Solution

from typing import Optional

# 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: Optional[TreeNode]) -> int:
        def dfs(node, direction, length):
            nonlocal max_length

            if not node:
                return
            
            # Update maximum length found so far
            max_length = max(max_length, length)

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

        return max_length

Step-by-Step Explanation

Step 1: Initialize DFS

We start DFS traversal from the root in both directions: left and right.

dfs(root, "left", 0)
dfs(root, "right", 0)

Step 2: Track Current Path Length

We pass the current length of the ZigZag path as a parameter and update it according to direction.

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

• Moving opposite to current direction increases the path length.
• Moving in the same direction resets the path length to 1.

Step 3: Update Maximum Path Length

max_length = max(max_length, length)

This ensures that we always track the longest ZigZag path found.

Step 4: Handle Base Case

If the node is None, simply return:

if not node:
    return

Step 5: Return Result

Finally, after DFS traversal completes:

return max_length

Time and Space Complexity

• Time Complexity: O(n) – Each node is visited once.
• Space Complexity: O(h) – Recursion stack space where h is the height of the tree.

Edge Cases

1. Empty Tree: Returns 0.
2. Single Node Tree: Returns 0 (no edges to form a ZigZag path).
3. Skewed Trees: Properly handles left or right skewed trees.

Real-World Applications

• Routing Algorithms: Alternating paths in tree-like networks.
• Game AI: Determine longest alternating move sequences.
• Data Structures Analysis: ZigZag paths in hierarchical or binary decision trees.
• Tree Pattern Detection: Detect alternating sequences in tree-based datasets.

Conclusion

The Longest ZigZag Path in a Binary Tree problem is an excellent exercise for mastering DFS traversal, recursion and path tracking. Understanding how to manage direction and path length enables you to solve complex tree traversal problems efficiently.

Practicing this problem prepares you for advanced binary tree questions, interviews and algorithmic challenges involving alternating paths.

Related Reads

• Path Sum III – LeetCode75 Python Solution Explained
• Count Good Nodes in a Binary Tree – LeetCode75 Python Solution Explained
• Maximum Depth of a Binary Tree – LeetCode75 Python Solution Explained
• Maximum Twin Sum of a Linked List – LeetCode75 Python Solution Explained
• Reverse Linked List – LeetCode75 Python Solution Explained

References

1. LeetCode 1372 – Longest ZigZag Path in a Binary Tree
2. Programiz – Binary Tree in Python
3. Wikipedia – Binary Tree