Longest Zigzag Path In A Binary Tree - Leetcode Solution

Problem Statement:

The problem is to find the length of the longest zigzag path in a binary tree. A zigzag path starts from a node in the binary tree and goes through the child nodes alternately, changing the direction at every level. The length of a zigzag path is the number of edges on the path.

Solution:

To find the longest zigzag path, we need to traverse the binary tree in a way that keeps track of the maximum length of the zigzag path encountered so far. We can do this by using a recursive function that takes a node and two flags indicating the direction of the previous traversal and the length of the zigzag path encountered.

The direction flag can take the values LEFT or RIGHT, indicating whether the previous traversal was to the left or right child of the node. The length variable keeps track of the length of the zigzag path encountered so far.

The base case of the recursive function is when the input node is null, in which case we return the length of the longest zigzag path encountered so far.

For each non-null node, we calculate the length of the zigzag path by checking the direction of the previous traversal and the direction of the current traversal. If the directions are different, we increment the length of the zigzag path. Otherwise, we reset the length of the zigzag path to one, indicating that the current node is the start of a new zigzag path.

To continue the recursive traversal, we call the function recursively on the left and right child nodes, passing the appropriate direction and length values.

Finally, we return the maximum length of the zigzag path encountered during the recursive traversal.

Here is the code for the solution:

enum Direction {LEFT, RIGHT};

int longestZigZag(TreeNode* root) {
    return max(longestZigZagHelper(root, LEFT, 0), longestZigZagHelper(root, RIGHT, 0));
}

int longestZigZagHelper(TreeNode* node, Direction dir, int length) {
    if (node == nullptr) {
        return length;
    }
    int max_length = length;
    if (dir == LEFT) {
        max_length = max(max_length, longestZigZagHelper(node->right, RIGHT, length + 1));
        max_length = max(max_length, longestZigZagHelper(node->left, LEFT, 1));
    } else {
        max_length = max(max_length, longestZigZagHelper(node->left, LEFT, length + 1));
        max_length = max(max_length, longestZigZagHelper(node->right, RIGHT, 1));
    }
    return max_length;
}

Time Complexity:

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. We visit each node once during the recursive traversal.

Space Complexity:

The space complexity of this solution is O(h), where h is the height of the binary tree. This is the maximum depth of the recursive call stack, which is the space required by the recursive solution.

1