We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest ZigZag Path in a Binary Tree

Difficulty: Medium

Problem Description

You are given the root of a binary tree. A ZigZag path for a binary tree is defined as follows:

  • 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.

Key Insights

  • A ZigZag path can start from any node and can move left or right at each step.
  • The length of the ZigZag path is determined by the number of direction changes made while traversing the tree.
  • Depth-first search (DFS) can be used to explore all possible ZigZag paths from each node.
  • Maintain two counts for each node: one for ZigZag paths starting by moving left and the other for moving right.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once. Space Complexity: O(H), where H is the height of the tree. This space is used by the call stack during recursion.

Solution

To solve this problem, we utilize a depth-first search (DFS) approach. We will traverse the binary tree while keeping track of the current length of the ZigZag path and the direction of the last move (left or right). For each node, we will:

  1. Check the length of the ZigZag path when moving left and when moving right.
  2. Update the maximum length found during the traversal.

The algorithm involves:

  • A recursive DFS function that takes the current node, the current length of the ZigZag path, and the direction of the last move as input.
  • Updating the maximum length found during the traversal.

Code Solutions

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(node, length, direction):
            if not node:
                return
            self.max_length = max(self.max_length, length)
            if direction == 'left':
                dfs(node.left, length + 1, 'right')  # move left, change direction to right
                dfs(node.right, 1, 'left')            # restart path moving right
            else:
                dfs(node.right, length + 1, 'left')  # move right, change direction to left
                dfs(node.left, 1, 'right')            # restart path moving left
        
        self.max_length = 0
        dfs(root, 0, 'left')  # start DFS from the root
        dfs(root, 0, 'right') # start DFS from the root
        return self.max_length
← Back to All Questions