> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/longest-zigzag-path-in-a-binary-tree.md).

# Longest ZigZag Path in a Binary Tree

Given a binary tree `root`, 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 then move to the right child of the current node otherwise move to the left child.
* Change the direction from right to left or right to left.
* Repeat the second and third step 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.leetcode.com/uploads/2020/01/22/sample_1_1702.png)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/01/22/sample_2_1702.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:**

* Each tree has at most `50000` nodes..
* Each node's value is between `[1, 100]`.

```java
class Solution {
    static int max = 0;

    public static int longestZigZag(TreeNode root) {
        if (root == null)
            return -1;// if null return -1
        max = 0;
        helper(root.right, 1, true);// go right
        helper(root.left, 1, false);// go left
        return max;
    }

    private static void helper(TreeNode root, int step, boolean isRight) {
        if (root == null)
            return;
        max = Math.max(max, step);
        if (isRight) {// if coming from right go left
            helper(root.left, step + 1, false);
            helper(root.right, 1, true);// try again from start
        } else {// else coming from left then go right
            helper(root.right, step + 1, true);
            helper(root.left, 1, false);
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/trees/longest-zigzag-path-in-a-binary-tree.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.