🚀 #LongestZigZagPath in a #BinaryTree | #LeetCode75 🔥 | #DFS #Recursion #Python #TreeTraversal

🔹 Problem Overview

In this problem, we need to find the longest ZigZag path in a given binary tree. A ZigZag path is defined as:

1️⃣ Start from any node in the tree.
2️⃣ Move left or right to the next child node.
3️⃣ After moving, change direction (left → right or right → left).
4️⃣ Keep moving until no more valid moves are possible.
5️⃣ The length of the ZigZag path is counted as number of moves (edges), not nodes.

✅ Approach: Depth-First Search (DFS) with Recursion

To solve this problem, we use Depth-First Search (DFS).

🔹 We traverse the binary tree while keeping track of:

✔️ Current direction (left or right).
✔️ Current ZigZag path length.
✔️ Maximum ZigZag length encountered.

🔹 Recursive function dfs(node, direction, length) works as follows:

1️⃣ Base Case: If node is None, return (end of a path).
3️⃣ Move to the left child if coming from the right, and reset length to 1 if the direction changes.
4️⃣ Move to the right child if coming from the left, and reset length to 1 if the direction changes.
5️⃣ Continue recursion until all paths are explored.

🔹 Python Solution (DFS Approach)

class TreeNode:
def __init__(self, val=0, left=None, right=None):

class Solution:
def longestZigZag(self, root):

def dfs(node, direction, length):
if not node:
return
# Update max length if a longer ZigZag path is found

# Move left (if coming from right) and reset direction
# Move right (if coming from left) and reset direction

# Start DFS from root, moving left and right

🔹 Complexity Analysis

✔ Time Complexity: O(N), where N is the number of nodes in the tree (since each node is visited once).
✔ Space Complexity: O(H), where H is the height of the tree (due to the recursion stack).

Worst case (H = N for skewed trees) → O(N) space.
Best case (H = log N for balanced trees) → O(log N) space.

🔹 Example Walkthrough

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]

Tree Representation:
1
\
1
/ \
1 1
/ \
1 1
/
1

Output: 3

Explanation: The longest ZigZag path is Right → Left → Right (marked in blue).

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]

Tree Representation:
1
/ \
1 1
\
1
/ \
1 1

Output: 4

Explanation: The longest ZigZag path is Left → Right → Left → Right.

Example 3:

Input: root = [1]

Output: 0

Explanation: The tree has only one node, so no ZigZag path is possible.

🔹 Why This Approach Works Well?

✅ Efficient Traversal: We use DFS to explore all paths in an optimized manner.
✅ Handles All Cases: Works for skewed, balanced, and full binary trees efficiently.

📌 Key Takeaways

🔹 Use DFS to traverse the tree while keeping track of the direction and length.
🔹 Update the maximum ZigZag path length dynamically.
🔹 Recursive approach ensures all paths are explored efficiently.
🔹 Optimal complexity makes it feasible for large inputs (N = 50,000).

🚀 Mastering DFS for tree problems like this helps in solving many LeetCode challenges efficiently!