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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest ZigZag Path in a Binary Tree

Number: 1474

Difficulty: Medium

Paid? No

Companies: Amazon, eBay

Problem Description

Given a binary tree, find the longest ZigZag path. A ZigZag path is defined as follows:

  • Choose any node and a direction (left or right).
  • If the direction is right, move to the right child; if left, move to the left child.
  • Change the direction (from right to left or from left to right) and continue.
  • The ZigZag length is the number of nodes visited minus one. For example, a single node has a length of 0.

Key Insights

  • The solution uses recursive DFS to explore every node.
  • For each node, we track two states:
    • ZigZag length when the last move was to the left.
    • ZigZag length when the last move was to the right.
  • At each node, these states are calculated based on the values returned from its children.
  • A global variable is maintained to update and record the maximum ZigZag path found.
  • Careful management of base cases (using -1 for null paths) ensures the correct length calculation.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(h), where h is the height of the tree, used by the recursion stack.

Solution

We solve the problem with DFS by visiting every node and, for each, computing two values: one corresponding to a path that last moved left (thus expecting a right move next) and the other for a path that last moved right (expecting a left move next). For null nodes, we return (-1, -1) so that when we add 1 for the current move, the length starts at 0. The global maximum is updated at every node. This approach leverages recursion to combine results from child nodes and continuously track the best ZigZag path length.

Code Solutions

# 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:
        # Initialize the global maximum zigzag length.
        self.max_zigzag = 0
        
        # DFS function returns a tuple (left_zigzag, right_zigzag)
        # left_zigzag: longest path if the last move was to the left (next must be right).
        # right_zigzag: longest path if the last move was to the right (next must be left).
        def dfs(node):
            if not node:
                # For null nodes, return -1 so that adding 1 gives 0 at the parent.
                return -1, -1
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # If moving left now (coming from a right move previously),
            # the zigzag path length is based on the right value from the left child.
            left_zigzag = left[1] + 1
            # Similarly, if moving right now (coming from a left move),
            # use the left value from the right child.
            right_zigzag = right[0] + 1
            
            # Update the global maximum with the highest value found.
            self.max_zigzag = max(self.max_zigzag, left_zigzag, right_zigzag)
            
            return left_zigzag, right_zigzag
        
        dfs(root)
        return self.max_zigzag
← Back to All Questions