1372. Longest ZigZag Path in a Binary Tree LeetCode Solution

In this guide, you will get 1372. Longest ZigZag Path in a Binary Tree LeetCode Solution with the best time and space complexity. The solution to Longest ZigZag Path in a Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest ZigZag Path in a Binary Tree solution in C++
Longest ZigZag Path in a Binary Tree solution in Java
Longest ZigZag Path in a Binary Tree solution in Python
Additional Resources

1372. Longest ZigZag Path in a Binary Tree LeetCode Solution image

Problem Statement of Longest ZigZag Path in a Binary Tree

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:

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:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

1372. Longest ZigZag Path in a Binary Tree LeetCode Solution in C++

struct T {
  int leftMax;
  int rightMax;
  int subtreeMax;
};

class Solution {
 public:
  int longestZigZag(TreeNode* root) {
    return dfs(root).subtreeMax;
  }

 private:
  T dfs(TreeNode* root) {
    if (root == nullptr)
      return {-1, -1, -1};
    const T left = dfs(root->left);
    const T right = dfs(root->right);
    const int leftZigZag = left.rightMax + 1;
    const int rightZigZag = right.leftMax + 1;
    const int subtreeMax =
        max({leftZigZag, rightZigZag, left.subtreeMax, right.subtreeMax});
    return {leftZigZag, rightZigZag, subtreeMax};
  }
};
/* code provided by PROGIEZ */

1372. Longest ZigZag Path in a Binary Tree LeetCode Solution in Java

class Solution {
  public int longestZigZag(TreeNode root) {
    return dfs(root).subtreeMax;
  }

  private record T(int leftMax, int rightMax, int subtreeMax) {}

  private T dfs(TreeNode root) {
    if (root == null)
      return new T(-1, -1, -1);
    T left = dfs(root.left);
    T right = dfs(root.right);
    final int leftZigZag = left.rightMax + 1;
    final int rightZigZag = right.leftMax + 1;
    final int subtreeMax =
        Math.max(Math.max(leftZigZag, rightZigZag), Math.max(left.subtreeMax, right.subtreeMax));
    return new T(leftZigZag, rightZigZag, subtreeMax);
  }
}
// code provided by PROGIEZ

1372. Longest ZigZag Path in a Binary Tree LeetCode Solution in Python

from dataclasses import dataclass


@dataclass(frozen=True)
class T:
  leftMax: int
  rightMax: int
  subtreeMax: int


class Solution:
  def longestZigZag(self, root: TreeNode | None) -> int:
    def dfs(root: TreeNode | None) -> T:
      if not root:
        return T(-1, -1, -1)
      left = dfs(root.left)
      right = dfs(root.right)
      leftZigZag = left.rightMax + 1
      rightZigZag = right.leftMax + 1
      subtreeMax = max(leftZigZag, rightZigZag,
                       left.subtreeMax, right.subtreeMax)
      return T(leftZigZag, rightZigZag, subtreeMax)

    return dfs(root).subtreeMax
 # code by PROGIEZ