1372. Longest ZigZag Path in a Binary Tree - Leetcode Solution

Code Implementation

# 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: Optional[TreeNode]) -> int:
        self.maxlen = 0

        def dfs(node, direction, length):
            if not node:
                return
            self.maxlen = max(self.maxlen, length)
            if direction == 'left':
                dfs(node.left, 'right', length + 1)
                dfs(node.right, 'left', 1)
            else:
                dfs(node.right, 'left', length + 1)
                dfs(node.left, 'right', 1)

        dfs(root.left, 'right', 1)
        dfs(root.right, 'left', 1)
        return self.maxlen

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };

class Solution {
public:
    int maxlen = 0;
    void dfs(TreeNode* node, bool isLeft, int length) {
        if (!node) return;
        maxlen = std::max(maxlen, length);
        if (isLeft) {
            dfs(node->left, false, length + 1);
            dfs(node->right, true, 1);
        } else {
            dfs(node->right, true, length + 1);
            dfs(node->left, false, 1);
        }
    }
    int longestZigZag(TreeNode* root) {
        dfs(root->left, false, 1);
        dfs(root->right, true, 1);
        return maxlen;
    }
};

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

class Solution {
    private int maxlen = 0;
    public int longestZigZag(TreeNode root) {
        dfs(root.left, false, 1);
        dfs(root.right, true, 1);
        return maxlen;
    }
    private void dfs(TreeNode node, boolean isLeft, int length) {
        if (node == null) return;
        maxlen = Math.max(maxlen, length);
        if (isLeft) {
            dfs(node.left, false, length + 1);
            dfs(node.right, true, 1);
        } else {
            dfs(node.right, true, length + 1);
            dfs(node.left, false, 1);
        }
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var longestZigZag = function(root) {
    let maxlen = 0;
    function dfs(node, isLeft, length) {
        if (!node) return;
        maxlen = Math.max(maxlen, length);
        if (isLeft) {
            dfs(node.left, false, length + 1);
            dfs(node.right, true, 1);
        } else {
            dfs(node.right, true, length + 1);
            dfs(node.left, false, 1);
        }
    }
    dfs(root.left, false, 1);
    dfs(root.right, true, 1);
    return maxlen;
};

Problem Description

Given the root of a binary tree, you are to find the length of the longest ZigZag path in the tree. A ZigZag path is defined as a sequence of nodes where each step alternates between moving to the left or right child. More formally, starting from any node, you can move to the left child, then to the right child of that node, then to the left child of that node, and so on, alternating directions at each step. The length of such a path is the number of edges (not nodes) traversed along the path.

You may start the ZigZag path from any node in the tree.
You must alternate between moving left and right at each step.
The path cannot revisit the same node.
The path can go as far as possible until it cannot continue in the required direction.

The input is given as a root node of a binary tree. The output should be a single integer representing the length of the longest ZigZag path found in the tree.

Thought Process

To solve this problem, we need to look for the longest sequence in the binary tree where the path alternates between left and right child nodes at each step. A brute-force approach might consider starting a ZigZag from every node and exploring all possible alternating paths, but this would be inefficient for large trees. Instead, we can observe that for every node, we can track two possibilities:

The longest ZigZag path starting by going left from this node.
The longest ZigZag path starting by going right from this node.

By using recursion (Depth-First Search), we can efficiently compute the ZigZag length at each node by considering both left and right directions and updating a global maximum as we traverse the tree.

Solution Approach

The solution uses a recursive Depth-First Search (DFS) to traverse the binary tree and keep track of the longest ZigZag path found so far. Here is the step-by-step approach:

Define a recursive function: The function takes the current node, the direction from which we arrived ('left' or 'right'), and the current ZigZag length.
Update the maximum: At each node, update the maximum ZigZag length found so far.
Recursive calls:
- If the previous move was to the left, the next move must be to the right. So, recursively call DFS on the right child with length incremented by 1, and on the left child with length reset to 1.
- If the previous move was to the right, the next move must be to the left. So, recursively call DFS on the left child with length incremented by 1, and on the right child with length reset to 1.
Start the process: Begin the DFS from the root's left and right children, considering both possible starting directions.
Return the result: After traversing the entire tree, return the maximum ZigZag length found.

This approach ensures that every possible ZigZag path is considered without redundant computations, and the global maximum is updated efficiently.

Example Walkthrough

Consider the following binary tree:

Start at node 1. Try both left and right directions.
From node 1 to node 2 (left), then to node 4 (right), then to node 6 (left): This is a left-right-left path. The length is 3 edges.
From node 1 to node 3 (right), then to node 5 (right) -- not a ZigZag, as direction did not alternate.
From node 3 to node 5 (right), then to node 7 (right) -- again, not a ZigZag.
The longest ZigZag path is from node 2 (start going right to node 4), then left to node 6, for a total length of 2. Alternatively, from node 1 to 2 to 4 to 6, which alternates left-right-left, for a length of 3.

As the DFS traverses, it checks all such paths, updating the maximum length each time a longer ZigZag is found.

Time and Space Complexity

Brute-force approach: For each node, you might try all possible ZigZag paths, leading to exponential time complexity in the worst case (O(2^N)), where N is the number of nodes.
Optimized recursive approach: Since each node is visited only a constant number of times (once for each direction), the time complexity is O(N), where N is the number of nodes in the tree.
Space complexity: The space used is O(H), where H is the height of the tree, due to the recursion stack. In the worst case (a skewed tree), H = N, so space is O(N).

Summary

The key to solving the Longest ZigZag Path in a Binary Tree problem efficiently is to use a recursive DFS that, for each node, considers both possible starting directions and keeps track of the current ZigZag length. By updating a global maximum during the traversal, we ensure that the longest path is found without redundant work. This approach is both elegant and efficient, with linear time complexity relative to the size of the tree.

AlgoMap.io

Want Help Cracking FAANG?