How do you solve Longest ZigZag Path in a Binary Tree on LeetCode?

Longest ZigZag Path in a Binary Tree (LeetCode #1372) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: ZigZag paths alternate between left and right, so tracking direction is crucial.

What is the brute force solution for Longest ZigZag Path in a Binary Tree?

The brute force approach for Longest ZigZag Path in a Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves exploring all possible paths in the binary tree to find the longest ZigZag path. This means we will start from each node and explore both left and right children recursively, switching directions at each step. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Longest ZigZag Path in a Binary Tree?

Clearly explain your thought process and the approach you are taking. Consider edge cases, such as trees with only one node. Practice writing clean and efficient recursive functions.

What are common mistakes when solving Longest ZigZag Path in a Binary Tree?

Not considering both directions from each node, leading to missed paths. Failing to reset the length correctly when switching directions.

#1372

Longest ZigZag Path in a Binary Tree

Medium

Dynamic ProgrammingTreeDepth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a depth-first search (DFS) approach that efficiently calculates the longest ZigZag path by maintaining the direction and length at each node. This method avoids redundant calculations by leveraging the properties of the tree structure.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to keep track of the maximum ZigZag length.
2Step 2: Create a recursive function that takes the current node, direction, and current length as parameters.
3Step 3: Update the maximum length at each node and recursively call the function for both left and right children, switching directions.

solution.py24 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def longestZigZag(self, root: TreeNode) -> int:
10        def dfs(node, direction, length):
11            if not node:
12                return
13            self.max_length = max(self.max_length, length)
14            if direction == 'left':
15                dfs(node.left, 'right', length + 1)
16                dfs(node.right, 'left', 1)
17            else:
18                dfs(node.right, 'left', length + 1)
19                dfs(node.left, 'right', 1)
20
21        self.max_length = 0
22        dfs(root, 'left', 0)
23        dfs(root, 'right', 0)
24        return self.max_length

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(n) due to the recursion stack in the worst case (for a skewed tree).

1ZigZag paths alternate between left and right, so tracking direction is crucial.
2Recursive depth-first search allows us to explore all possible paths efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.