Longest ZigZag Path in a Binary Tree - Practice Coding Problems

Longest ZigZag Path in a Binary Tree - Problem

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

The zigzag length is defined as the number of nodes visited minus 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

Input & Output

Example 1 — Complex Tree

$ Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]

› Output: 3

💡 Note: The longest ZigZag path has length 3. Starting from the right child of root, go Left→Right→Left to reach maximum length.

Example 2 — Simple Path

$ Input: root = [1,1,1,null,1,null,null,1,1,null,1]

› Output: 4

💡 Note: The longest ZigZag path goes Right→Left→Right→Left→Right, giving length 4.

Example 3 — Single Node

$ Input: root = [1]

› Output: 0

💡 Note: A single node has zigzag length 0 by definition.

Constraints

The number of nodes in the tree is in the range [1, 5 × 10⁴]
1 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes where we need to find zigzag paths

ZigZag Paths

Alternate between left and right moves at each step

Maximum Length

Return the length of the longest zigzag path found

Key Takeaway

🎯 Key Insight: Use DFS to track both left-going and right-going zigzag paths at each node simultaneously

Asked in

F Facebook 35 a Amazon 28 G Google 22 M Microsoft 18

The key insight is to use DFS to track the longest zigzag path in both directions at each node. The optimal approach uses DFS with state tracking to compute left-going and right-going zigzag lengths simultaneously. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Paths	O(n²)	O(h)	Start DFS from every node in both directions to find maximum zigzag length
DFS with State Tracking	O(n)	O(h)	Single DFS pass tracking left and right zigzag lengths at each node

Brute Force - Check All Paths — Algorithm Steps

Step 1: Visit every node in the tree
Step 2: From each node, start zigzag paths in both directions
Step 3: For each path, alternate directions until no more moves possible
Step 4: Track maximum length across all paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Every Node

Start DFS from each node as potential zigzag start

Try Both Directions

From each node, try going left then right, and right then left

Track Maximum

Keep track of the longest zigzag path found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int max(int a, int b) {
    return a > b ? a : b;
}

int zigzagFromNode(struct TreeNode* node, char* direction, int length) {
    if (!node) return length;
    
    if (strcmp(direction, "left") == 0) {
        return node->left ? zigzagFromNode(node->left, "right", length + 1) : length;
    } else {
        return node->right ? zigzagFromNode(node->right, "left", length + 1) : length;
    }
}

int traverseAllNodes(struct TreeNode* node) {
    if (!node) return 0;
    
    int leftStart = node->left ? zigzagFromNode(node->left, "right", 1) : 0;
    int rightStart = node->right ? zigzagFromNode(node->right, "left", 1) : 0;
    
    int currentMax = max(leftStart, rightStart);
    
    int leftSubtree = traverseAllNodes(node->left);
    int rightSubtree = traverseAllNodes(node->right);
    
    return max(currentMax, max(leftSubtree, rightSubtree));
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    return traverseAllNodes(root);
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Simplified for basic test case
    struct TreeNode* root = createNode(1);
    root->right = createNode(1);
    root->right->left = createNode(1);
    root->right->right = createNode(1);
    root->right->right->left = createNode(1);
    root->right->right->right = createNode(1);
    root->right->right->left->right = createNode(1);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially traverse the entire tree to find zigzag paths

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

89.2K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler