Longest ZigZag Path in a Binary Tree

Medium

Asked by:

30 views

Topics:

TreesDynamic ProgrammingRecursion

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 * 10⁴].
1 <= Node.val <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree be empty? If so, what should I return?
What integer values can the nodes hold? Can they be negative, zero, or floating-point numbers?
What defines the 'length' of a zigzag path? Is it the number of nodes or the number of edges?
If there are multiple zigzag paths with the same maximum length, is it sufficient to return the length of any one of them?
Is a single node a valid zigzag path of length 0 (if counting edges) or 1 (if counting nodes)?

Brute Force Solution

Approach

The brute force way to find the longest zigzag path explores every single path through the tree. We start at the root and investigate all possible routes, going left then right, or right then left, making sure to follow the zigzag pattern.

Here's how the algorithm would work step-by-step:

Begin at the very top of the tree, which is the starting point.
From there, try going down the left path first, and see how far you can go while alternating directions (left, then right, then left...).
Record the length of this zigzag path.
Now, go back to the top and try going down the right path first, and again see how far you can go while alternating directions (right, then left, then right...).
Record the length of this zigzag path too.
Repeat this process for every single starting point in the tree - every single node.
Compare all the zigzag path lengths you have recorded, and select the very longest one.

Code Implementation

def longest_zigzag_brute_force(root):
    def zigzag_length(node, go_left, length):
        if not node:
            return length

        if go_left:
            # Explore zigzag path going left, then right
            left_path_length = zigzag_length(node.left, False, length + 1)

            # If we didn't go left, explore starting right too
            right_path_length = zigzag_length(node.right, True, 1)
            return max(left_path_length, right_path_length)
        else:
            # Explore zigzag path going right, then left
            right_path_length = zigzag_length(node.right, True, length + 1)

            # If we didn't go right, explore starting left too
            left_path_length = zigzag_length(node.left, False, 1)
            return max(right_path_length, left_path_length)

    def explore_all_paths(node):
        if not node:
            return 0

        # Find the longest zigzag path starting from this node
        start_left = zigzag_length(node.left, False, 1)

        # Find the longest zigzag path starting from this node
        start_right = zigzag_length(node.right, True, 1)

        # Recursively explore all other nodes in the tree
        longest_in_subtree = max(explore_all_paths(node.left), explore_all_paths(node.right))

        return max(start_left, start_right, longest_in_subtree)

    # Start the process from the root
    return explore_all_paths(root)

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach explores every possible path starting from each of the n nodes in the tree. For each node, finding the longest zigzag path potentially requires visiting all other nodes in the worst case to find the longest zigzag sequence originating from that node. Consequently, the algorithm performs an operation that, in the worst case, involves visiting n nodes for each of the n nodes in the tree, leading to approximately n * n operations. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The brute force approach explores every path in the binary tree using recursion. In the worst-case scenario (a skewed tree), the recursion depth can be equal to the number of nodes N, where N is the total number of nodes in the tree. Each recursive call adds a new frame to the call stack, which requires storing local variables and the return address. Therefore, the auxiliary space used by the recursion stack can grow up to O(N) in the worst case.

Optimal Solution

Approach

The goal is to find the longest path in a tree that alternates directions (left, right, left, etc.). We can solve this efficiently by exploring each branch of the tree while keeping track of the longest zigzag path we've seen so far. This avoids unnecessary recalculations and directly finds the maximum length.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, the root.
For each branch (left and right) going down from a point, consider the path we're currently on.
Keep track of two things for each branch: the length of the longest zigzag path if we ended on a left turn, and the length if we ended on a right turn.
When we move down to the next point, update these lengths. If we're taking a left turn, the new 'left turn' length is 1 plus the previous point's 'right turn' length. If we're taking a right turn, it's 1 plus the previous point's 'left turn' length.
At each point, remember the longest path length we've seen so far, whether it ended on a left or right turn.
Continue this process until we've explored every branch of the tree.
The overall longest path length we remembered is the answer.

Code Implementation

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

def longestZigZag(root):
    longest_path = 0

    def depthFirstSearch(node):
        nonlocal longest_path

        if not node:
            return -1, -1

        # Get lengths from the left
        left_length_right, left_length_left = depthFirstSearch(node.left)
        
        # Get lengths from the right
        right_length_right, right_length_left = depthFirstSearch(node.right)

        current_left_path_length = left_length_right + 1
        current_right_path_length = right_length_left + 1

        # Update the longest path encountered
        longest_path = max(longest_path, current_left_path_length, \
                           current_right_path_length)

        return current_left_path_length, current_right_path_length

    depthFirstSearch(root)
    return longest_path

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a depth-first traversal of the binary tree. Each node in the tree is visited exactly once. At each node, a constant amount of work is performed to update the longest zigzag path lengths based on whether we arrived from the left or right. Therefore, the time complexity is directly proportional to the number of nodes in the tree, which is n. Consequently, the overall time complexity is O(n).

Space Complexity

O(H) – The space complexity is primarily determined by the recursion depth of the depth-first search (DFS). In the worst-case scenario, the recursion can go as deep as the height (H) of the binary tree. Each recursive call adds a new frame to the call stack, requiring storage for local variables (left and right zigzag path lengths) and the return address. Therefore, the auxiliary space used is proportional to the height of the tree. In the worst case, for a skewed tree H can be N, but in the best and average cases for a balanced tree H would be log N.

Edge Cases

Case	How to Handle
Null root node	Return 0 immediately, as an empty tree has no path.
Single node tree	Return 0, as a single node doesn't have a zigzag path.
Tree with only left children	The algorithm should correctly calculate the longest path down only left children.
Tree with only right children	The algorithm should correctly calculate the longest path down only right children.
Perfectly balanced binary tree	The algorithm should efficiently traverse the balanced tree without excessive recursion.
Highly unbalanced (skewed) tree	The algorithm should handle potential stack overflow issues with deep recursion by considering iterative approaches or tail recursion optimization if available.
Large tree (nearing memory limits)	Be mindful of memory usage if storing path information; consider more space-efficient approaches like keeping track of the path length only.
Integer overflow potential when calculating path length	Ensure that the data type used to store path length (likely integer) is sufficiently large to avoid overflow in extreme cases.

Null root node

How to Handle:

Return 0 immediately, as an empty tree has no path.

Single node tree

How to Handle:

Return 0, as a single node doesn't have a zigzag path.

Tree with only left children

How to Handle:

The algorithm should correctly calculate the longest path down only left children.

Tree with only right children

How to Handle:

The algorithm should correctly calculate the longest path down only right children.

Perfectly balanced binary tree

How to Handle:

The algorithm should efficiently traverse the balanced tree without excessive recursion.

Highly unbalanced (skewed) tree

How to Handle:

The algorithm should handle potential stack overflow issues with deep recursion by considering iterative approaches or tail recursion optimization if available.

Large tree (nearing memory limits)

How to Handle:

Be mindful of memory usage if storing path information; consider more space-efficient approaches like keeping track of the path length only.

Integer overflow potential when calculating path length

How to Handle:

Ensure that the data type used to store path length (likely integer) is sufficiently large to avoid overflow in extreme cases.