# Longest ZigZag Path in a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/longest-zigzag-path-in-a-binary-tree
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [eBay](https://scaleengineer.com/companies/ebay)
---
## Problem
You are given the `root` of a binary tree.

A ZigZag path for a binary tree is defined as follow:

* Choose **any** node in the binary tree and a direction (right or left).
* If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
* Change the direction from right to left or from left to right.
* Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1\. (A single node has a length of 0).

Return _the longest **ZigZag** path contained in that tree_.

**Example 1:**

![](https://assets.glich.co/dsa/longest-zigzag-path-in-a-binary-tree/image0.png) 

**Input:** root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
**Output:** 3
**Explanation:** Longest ZigZag path in blue nodes (right -> left -> right).

**Example 2:**

![](https://assets.glich.co/dsa/longest-zigzag-path-in-a-binary-tree/image1.png) 

**Input:** root = [1,1,1,null,1,null,null,1,1,null,1]
**Output:** 4
**Explanation:** Longest ZigZag path in blue nodes (left -> right -> left -> right).

**Example 3:**

**Input:** root = [1]
**Output:** 0

**Constraints:**

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

# Approaches
## Brute Force from Every Node
This approach iterates through every node in the tree. For each node, it treats it as a potential starting point for a ZigZag path. From each node, it calculates the length of the longest possible ZigZag path starting with a left move and the longest path starting with a right move. The overall maximum length found among all starting nodes is the result.
**Time:** O(N*H) or O(N^2) in the worst case. The `traverse` function visits each of the N nodes. For each node, `calculatePath` can traverse up to the height H of the tree. In the worst case of a skewed tree, H is N, leading to O(N^2) complexity. · **Space:** O(H) or O(N) in the worst case. The space complexity is determined by the recursion stack depth of the traversal. In a balanced tree, it's O(log N), but in a skewed tree, it can be O(N).
**Pros:** Conceptually simple and directly follows the problem definition.
**Cons:** Highly inefficient due to a large number of redundant computations.; For each node, it re-calculates path segments that have already been computed when processing child nodes.
### Explanation
The brute-force method systematically explores every possible ZigZag path. We can achieve this by traversing the entire tree. For every single node we encounter, we consider it as the starting point of a new ZigZag path. Since a path can begin by going either left or right, we explore both possibilities from each node.

We can implement a `traverse` function that visits each node. Inside this function, for the current node, we will have two loops. One loop simulates a ZigZag path starting with a left turn, and the other simulates a path starting with a right turn. These loops follow the alternating path rule, incrementing a counter for the length at each step and updating a global maximum. This ensures that we check every path starting from every node.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxLength = 0;

    public int longestZigZag(TreeNode root) {
        traverse(root);
        return maxLength;
    }

    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }

        // Calculate longest ZigZag path starting at the current node
        // Case 1: Path starts by going left
        calculatePath(node.left, false, 1); // Next move must be right
        // Case 2: Path starts by going right
        calculatePath(node.right, true, 1); // Next move must be left

        // Traverse the rest of the tree
        traverse(node.left);
        traverse(node.right);
    }

    // Helper to trace a single ZigZag path and update maxLength
    private void calculatePath(TreeNode node, boolean goLeft, int length) {
        if (node == null) {
            // Path ended at the parent of this null node.
            // The actual path length is length - 1.
            maxLength = Math.max(maxLength, length - 1);
            return;
        }

        maxLength = Math.max(maxLength, length);

        if (goLeft) {
            // Current direction is left, so next must be right
            calculatePath(node.left, false, length + 1);
        } else {
            // Current direction is right, so next must be left
            calculatePath(node.right, true, length + 1);
        }
    }
}
```
### Algorithm
- Create a main function `longestZigZag(root)` that initializes a global maximum length variable, `maxLength`, to 0.
- This function will call a traversal function, `traverse(node)`, on the root to visit every node in the tree.
- The `traverse(node)` function will iterate through the tree (e.g., using pre-order traversal).
- For each `node` visited, it will calculate the longest ZigZag path starting from this `node`.
- To do this, it will simulate two paths:
  1. A path starting by moving to the left child.
  2. A path starting by moving to the right child.
- An iterative loop can be used for this simulation. For a path starting left, it moves to `node.left`, increments the length, then alternates between moving right and left until it hits a `null` node.
- During this simulation, `maxLength` is updated at each step.
- The same process is repeated for a path starting to the right.
- After the `traverse` function has visited all nodes, `maxLength` will hold the final answer.

## Optimal Single-Pass DFS
A more efficient approach is to use a single Depth First Search (DFS) pass. By employing a post-order traversal, we can compute the necessary information for a node based on the results from its children. For each node, we calculate the length of the longest ZigZag path starting at that node and going left, and the length of the path starting at that node and going right. This information is then 'bubbled up' to the parent node, which uses it to compute the lengths of its own starting paths. A global variable is used to keep track of the maximum length found at any point in the traversal.
**Time:** O(N). The algorithm traverses each node in the tree exactly once. · **Space:** O(H) or O(N) in the worst case. The space is used by the recursion stack. For a balanced tree, this is O(log N). For a skewed tree, it becomes O(N).
**Pros:** Optimal time complexity of O(N) as it visits each node only once.; Efficient use of space, proportional to the height of the tree.
**Cons:** The recursive logic, especially the meaning of the returned array, can be slightly less intuitive to grasp initially compared to the brute-force approach.
### Explanation
This optimal solution avoids re-computation by solving the problem in a single pass using a post-order DFS traversal. The core idea is to use the return value of the recursive calls to pass information up the tree.

Our recursive function, `dfs(node)`, will return an array of two integers for each node. The first element will be the length of the longest ZigZag path starting at `node` with a left move, and the second will be the length of the path starting with a right move.

When `dfs(node)` is called:
1. It first calls itself on its left and right children.
2. It receives the results from its children. For example, `leftResult` from `dfs(node.left)` contains the lengths of paths starting at `node.left`.
3. To find the length of a ZigZag path starting at `node` and going left, we take one step to `node.left` (length 1) and then continue the ZigZag. The next move must be to the right. The length of the longest ZigZag path starting from `node.left` and going right is given by `leftResult[1]`. So, the total length is `1 + leftResult[1]`.
4. Similarly, the length of a path starting at `node` and going right is `1 + rightResult[0]`.
5. We update a global `maxLength` with the maximum of these two calculated lengths. This ensures we track the longest path found anywhere in the tree.
6. Finally, the function returns the newly computed lengths for `node` to its parent.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxLength = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root);
        return maxLength;
    }

    /**
     * Performs a post-order traversal to calculate ZigZag path lengths.
     * @return an array of two elements:
     *         result[0] = longest ZigZag path starting from 'node' and going LEFT.
     *         result[1] = longest ZigZag path starting from 'node' and going RIGHT.
     */
    private int[] dfs(TreeNode node) {
        if (node == null) {
            // Base case: no path exists from a null node.
            // -1 helps in calculation: 1 + (-1) = 0 for a path of a single node.
            return new int[]{-1, -1};
        }

        // Recursively get results from children
        int[] leftResult = dfs(node.left);
        int[] rightResult = dfs(node.right);

        // Calculate path starting at current node and going left.
        // This path continues from the left child by going right.
        int pathStartingLeft = 1 + leftResult[1];

        // Calculate path starting at current node and going right.
        // This path continues from the right child by going left.
        int pathStartingRight = 1 + rightResult[0];

        // Update the global maximum length found so far.
        maxLength = Math.max(maxLength, Math.max(pathStartingLeft, pathStartingRight));

        // Return the lengths of paths starting at the current node for the parent.
        return new int[]{pathStartingLeft, pathStartingRight};
    }
}
```
### Algorithm
- Use a single Depth First Search (DFS) traversal, specifically a post-order traversal.
- Define a recursive helper function, `dfs(node)`, that returns information about paths starting at `node`.
- The `dfs(node)` function will return an array of two integers: `[leftPath, rightPath]`.
  - `leftPath`: The length of the longest ZigZag path that starts at `node` and first goes to the left.
  - `rightPath`: The length of the longest ZigZag path that starts at `node` and first goes to the right.
- The base case for the recursion is when `node` is `null`. In this case, return `[-1, -1]` to indicate that no path exists, which simplifies the calculation for the parent.
- For a non-null `node`, recursively call `dfs` on its children: `leftResult = dfs(node.left)` and `rightResult = dfs(node.right)`.
- To calculate `leftPath` for the current `node`: a path going left from `node` must then continue from `node.left` by going right. So, `leftPath = 1 + leftResult[1]`.
- Similarly, `rightPath = 1 + rightResult[0]`.
- Maintain a global `maxLength` variable. After computing `leftPath` and `rightPath` for the current `node`, update `maxLength = max(maxLength, leftPath, rightPath)`.
- The `dfs` function returns the `[leftPath, rightPath]` array for its parent to use.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; public int longestZigZag ( TreeNode root ) { dfs ( root , 0 , 0 ); return ans ; } private void dfs ( TreeNode root , int l , int r ) { if ( root == null ) { return ; } ans = Math . max ( ans , Math . max ( l , r )); dfs ( root . left , r + 1 , 0 ); dfs ( root . right , 0 , l + 1 ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int ans = 0 ; int longestZigZag ( TreeNode * root ) { dfs ( root , 0 , 0 ); return ans ; } void dfs ( TreeNode * root , int l , int r ) { if ( ! root ) return ; ans = max ( ans , max ( l , r )); dfs ( root -> left , r + 1 , 0 ); dfs ( root -> right , 0 , l + 1 ); } };
```

### Python

```python
# 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
```