Binary Tree Zigzag Level Order Traversal

🎯

Binary Tree Zigzag Level Order Traversal

mediumTREEAmazonFacebookGoogle

Imagine you are organizing a company hierarchy chart where you want to list employees level by level, but alternate the direction of listing each level to make the chart visually engaging.

💡 This problem is a variation of the classic level order traversal of a binary tree. Beginners often struggle because they need to alternate the direction of traversal at each level, which requires careful control of the order nodes are processed and stored.

📋

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). Input: root node of a binary tree. Output: a list of lists of integers representing node values in zigzag level order.

The number of nodes in the tree is in the range [0, 10^5].-10^9 <= Node.val <= 10^9

💡

Example

Input"root = [3,9,20,null,null,15,7]"

Output[[3],[20,9],[15,7]]

Level 0: left to right → [3]; Level 1: right to left → [20,9]; Level 2: left to right → [15,7]

• Empty tree → []
• Tree with only one node → [[node_value]]
• Tree with all nodes only on left → zigzag alternates but only one node per level
• Tree with all nodes only on right → zigzag alternates but only one node per level

⚠️

Common Mistakes

Forgetting to reverse or alternate direction at every other level

Output is just normal level order traversal, failing the zigzag requirement

✅ Add a flag to track level parity and reverse or insert nodes accordingly

Reversing the list in-place but forgetting to copy it before appending

Subsequent levels get affected or output is corrupted

✅ Reverse a copy or reverse before appending to result

Using queue operations inefficiently, e.g., popping from front of array in JavaScript

Code runs slowly or times out on large inputs

✅ Use deque or linked list structures where possible for O(1) pops

Pushing children in wrong order in two stacks approach

Zigzag order is incorrect, levels appear scrambled

✅ Carefully push left then right or right then left depending on direction

Not handling empty tree input

Code throws null pointer or index errors

✅ Check for null root at start and return empty list

🧠

Brute Force (Level Order Traversal + Reverse Every Other Level)

💡 This approach builds on the classic level order traversal by reversing the order of nodes at every alternate level after the traversal. It is straightforward and helps beginners understand the problem's core requirement before optimizing.

Intuition

Perform a normal BFS level order traversal, collect nodes level by level, then reverse the nodes at every odd-indexed level to achieve the zigzag pattern.

Algorithm

1. Use a queue to perform a standard BFS level order traversal.
2. For each level, collect all node values in a list.
3. If the current level is odd-numbered, reverse the list before adding it to the result.
4. Continue until all levels are processed.

💡 The key difficulty is remembering to reverse the nodes at every alternate level after collecting them, which is easy to forget.

</>

Code

from collections import deque

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

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    level = 0
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        if level % 2 == 1:
            current_level.reverse()
        result.append(current_level)
        level += 1
    return result

# Driver code to test
if __name__ == '__main__':
    # Construct the tree [3,9,20,null,null,15,7]
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(zigzagLevelOrder(root))

Line Notes

if not root:Handle empty tree edge case immediately to avoid errors.

queue = deque([root])Initialize queue with root to start BFS traversal.

for _ in range(level_size):Process all nodes at the current level.

if level % 2 == 1:Reverse current level nodes for odd levels to achieve zigzag.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            if (level % 2 == 1) {
                Collections.reverse(currentLevel);
            }
            result.add(currentLevel);
            level++;
        }
        return result;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.zigzagLevelOrder(root));
    }
}

Line Notes

if (root == null) return result;Immediately return empty list if tree is empty.

Queue<TreeNode> queue = new LinkedList<>();Use queue to perform BFS traversal.

for (int i = 0; i < size; i++) {Process all nodes at current level.

if (level % 2 == 1) { Collections.reverse(currentLevel); }Reverse nodes at odd levels to get zigzag order.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    int level = 0;
    while (!q.empty()) {
        int size = q.size();
        vector<int> currentLevel;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            currentLevel.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        if (level % 2 == 1) {
            reverse(currentLevel.begin(), currentLevel.end());
        }
        result.push_back(currentLevel);
        level++;
    }
    return result;
}

// Driver code
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    vector<vector<int>> res = zigzagLevelOrder(root);
    for (auto &level : res) {
        for (int val : level) cout << val << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

if (!root) return result;Return empty vector if tree is empty to avoid errors.

queue<TreeNode*> q;Queue used for BFS traversal of tree nodes.

for (int i = 0; i < size; i++) {Process all nodes at the current level.

if (level % 2 == 1) { reverse(...); }Reverse the current level's nodes to achieve zigzag order.

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function zigzagLevelOrder(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];
    let level = 0;
    while (queue.length > 0) {
        const size = queue.length;
        const currentLevel = [];
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        if (level % 2 === 1) {
            currentLevel.reverse();
        }
        result.push(currentLevel);
        level++;
    }
    return result;
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(zigzagLevelOrder(root));

Line Notes

if (!root) return [];Handle empty tree edge case immediately.

const queue = [root];Initialize queue with root node for BFS traversal.

for (let i = 0; i < size; i++) {Process all nodes at current level.

if (level % 2 === 1) { currentLevel.reverse(); }Reverse nodes at odd levels to get zigzag order.

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit each node exactly once in BFS, so time is O(n). The queue and result store all nodes, so space is O(n).

💡 For n=1000 nodes, this means roughly 1000 operations and storing 1000 values, which is efficient for typical interview constraints.

Interview Verdict: Accepted

This approach is accepted and easy to implement, but reversing lists repeatedly can be optimized.

🧠

Better (Using Deque to Avoid Reversing Levels)

💡 Instead of reversing the list after collecting nodes, we use a deque to append nodes in the correct order during traversal, saving time and improving clarity.

Intuition

Use a deque to add node values either to the end or the front depending on the current level's direction, so the zigzag order is built on the fly.

Algorithm

1. Initialize a queue for BFS and a deque for current level nodes.
2. For each level, depending on direction, append node values to the deque's end or front.
3. Add children to the queue in normal order for next level processing.
4. Convert deque to list and add to result, then toggle direction.

💡 The trick is to use the deque's ability to add elements at both ends to maintain zigzag order without reversing.

</>

Code

from collections import deque

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

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True
    while queue:
        level_size = len(queue)
        current_level = deque()
        for _ in range(level_size):
            node = queue.popleft()
            if left_to_right:
                current_level.append(node.val)
            else:
                current_level.appendleft(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(list(current_level))
        left_to_right = not left_to_right
    return result

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(zigzagLevelOrder(root))

Line Notes

queue = deque([root])Initialize BFS queue with root node.

left_to_right = TrueBoolean flag to track direction of traversal per level.

if left_to_right: current_level.append(node.val)Append to right end if left to right.

else: current_level.appendleft(node.val)Append to left end if right to left to build zigzag.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> currentLevel = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    currentLevel.addLast(node.val);
                } else {
                    currentLevel.addFirst(node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(currentLevel);
            leftToRight = !leftToRight;
        }
        return result;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.zigzagLevelOrder(root));
    }
}

Line Notes

boolean leftToRight = true;Flag to track direction of traversal for each level.

LinkedList<Integer> currentLevel = new LinkedList<>();Use LinkedList to add elements at both ends efficiently.

if (leftToRight) { currentLevel.addLast(node.val); }Add to end if traversing left to right.

else { currentLevel.addFirst(node.val); }Add to front if traversing right to left.

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;
    while (!q.empty()) {
        int size = q.size();
        deque<int> currentLevel;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            if (leftToRight) {
                currentLevel.push_back(node->val);
            } else {
                currentLevel.push_front(node->val);
            }
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.emplace_back(vector<int>(currentLevel.begin(), currentLevel.end()));
        leftToRight = !leftToRight;
    }
    return result;
}

// Driver code
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    vector<vector<int>> res = zigzagLevelOrder(root);
    for (auto &level : res) {
        for (int val : level) cout << val << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

bool leftToRight = true;Track direction of traversal for each level.

deque<int> currentLevel;Deque allows insertion at both ends efficiently.

if (leftToRight) { currentLevel.push_back(node->val); }Add to back if left to right.

else { currentLevel.push_front(node->val); }Add to front if right to left.

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function zigzagLevelOrder(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];
    let leftToRight = true;
    while (queue.length > 0) {
        const size = queue.length;
        const currentLevel = [];
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (leftToRight) {
                currentLevel.push(node.val);
            } else {
                currentLevel.unshift(node.val);
            }
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(currentLevel);
        leftToRight = !leftToRight;
    }
    return result;
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(zigzagLevelOrder(root));

Line Notes

let leftToRight = true;Boolean flag to track current level traversal direction.

const currentLevel = [];Array to store current level nodes in zigzag order.

if (leftToRight) { currentLevel.push(node.val); }Add to end if traversing left to right.

else { currentLevel.unshift(node.val); }Add to front if traversing right to left.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once. Using deque avoids reversing, so time remains O(n). Space is O(n) for queue and result.

💡 For n=1000, this approach saves time by avoiding repeated reversals, making it more efficient in practice.

Interview Verdict: Accepted

This approach is more efficient than brute force and preferred in interviews for clarity and performance.

🧠

Optimal (Two Stacks to Control Zigzag Order)

💡 Using two stacks to alternate the order of node processing naturally produces the zigzag pattern without reversing or complex insertions.

Intuition

Use one stack to process nodes from left to right, and another stack to process nodes from right to left, alternating between them for each level.

Algorithm

1. Initialize two stacks: currentLevel and nextLevel.
2. Push root to currentLevel stack.
3. While currentLevel is not empty, pop nodes and add their values to current level list.
4. Push children to nextLevel stack in order depending on current direction.
5. Swap stacks and toggle direction after finishing each level.

💡 The main challenge is managing the order of pushing children to the next stack to maintain zigzag order.

</>

Code

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

def zigzagLevelOrder(root):
    if not root:
        return []
    currentLevel = [root]
    nextLevel = []
    result = []
    left_to_right = True
    while currentLevel:
        level_vals = []
        while currentLevel:
            node = currentLevel.pop()
            level_vals.append(node.val)
            if left_to_right:
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            else:
                if node.right:
                    nextLevel.append(node.right)
                if node.left:
                    nextLevel.append(node.left)
        result.append(level_vals)
        currentLevel, nextLevel = nextLevel, []
        left_to_right = not left_to_right
    return result

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(zigzagLevelOrder(root))

Line Notes

currentLevel = [root]Start with root in current level stack.

while currentLevel:Process nodes level by level using stacks.

node = currentLevel.pop()Pop nodes from current stack to process in correct order.

if left_to_right: ... else: ...Push children in order depending on traversal direction.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> currentLevel = new Stack<>();
        Stack<TreeNode> nextLevel = new Stack<>();
        currentLevel.push(root);
        boolean leftToRight = true;
        while (!currentLevel.isEmpty()) {
            List<Integer> levelVals = new ArrayList<>();
            while (!currentLevel.isEmpty()) {
                TreeNode node = currentLevel.pop();
                levelVals.add(node.val);
                if (leftToRight) {
                    if (node.left != null) nextLevel.push(node.left);
                    if (node.right != null) nextLevel.push(node.right);
                } else {
                    if (node.right != null) nextLevel.push(node.right);
                    if (node.left != null) nextLevel.push(node.left);
                }
            }
            result.add(levelVals);
            Stack<TreeNode> temp = currentLevel;
            currentLevel = nextLevel;
            nextLevel = temp;
            nextLevel.clear();
            leftToRight = !leftToRight;
        }
        return result;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.zigzagLevelOrder(root));
    }
}

Line Notes

Stack<TreeNode> currentLevel = new Stack<>();Stack to hold nodes of current level.

while (!currentLevel.isEmpty()) {Process all nodes in current level stack.

TreeNode node = currentLevel.pop();Pop nodes to process in correct order.

if (leftToRight) { ... } else { ... }Push children in order depending on direction.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    stack<TreeNode*> currentLevel;
    stack<TreeNode*> nextLevel;
    currentLevel.push(root);
    bool leftToRight = true;
    while (!currentLevel.empty()) {
        vector<int> levelVals;
        while (!currentLevel.empty()) {
            TreeNode* node = currentLevel.top(); currentLevel.pop();
            levelVals.push_back(node->val);
            if (leftToRight) {
                if (node->left) nextLevel.push(node->left);
                if (node->right) nextLevel.push(node->right);
            } else {
                if (node->right) nextLevel.push(node->right);
                if (node->left) nextLevel.push(node->left);
            }
        }
        result.push_back(levelVals);
        swap(currentLevel, nextLevel);
        while (!nextLevel.empty()) nextLevel.pop();
        leftToRight = !leftToRight;
    }
    return result;
}

// Driver code
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    vector<vector<int>> res = zigzagLevelOrder(root);
    for (auto &level : res) {
        for (int val : level) cout << val << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

stack<TreeNode*> currentLevel;Stack to hold nodes of current level for processing.

while (!currentLevel.empty()) {Process all nodes in current level stack.

TreeNode* node = currentLevel.top(); currentLevel.pop();Pop nodes to process in correct order.

if (leftToRight) { ... } else { ... }Push children in order depending on traversal direction.

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function zigzagLevelOrder(root) {
    if (!root) return [];
    let currentLevel = [root];
    let nextLevel = [];
    const result = [];
    let leftToRight = true;
    while (currentLevel.length > 0) {
        const levelVals = [];
        while (currentLevel.length > 0) {
            const node = currentLevel.pop();
            levelVals.push(node.val);
            if (leftToRight) {
                if (node.left) nextLevel.push(node.left);
                if (node.right) nextLevel.push(node.right);
            } else {
                if (node.right) nextLevel.push(node.right);
                if (node.left) nextLevel.push(node.left);
            }
        }
        result.push(levelVals);
        [currentLevel, nextLevel] = [nextLevel, []];
        leftToRight = !leftToRight;
    }
    return result;
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(zigzagLevelOrder(root));

Line Notes

let currentLevel = [root];Initialize current level stack with root node.

while (currentLevel.length > 0) {Process nodes level by level using stacks.

const node = currentLevel.pop();Pop nodes to process in correct order for zigzag.

if (leftToRight) { ... } else { ... }Push children in order depending on direction.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once. Using stacks avoids reversing or deque operations, maintaining O(n) time and space.

💡 For n=1000, this approach is efficient and elegant, often preferred in interviews for its clarity.

Interview Verdict: Accepted

This is an optimal and clean approach that naturally fits the zigzag traversal pattern.

📊

All Approaches - One-Glance Tradeoffs

💡 The deque and two stacks approaches are preferred in interviews for their efficiency and clarity. The brute force approach is useful to explain the problem but less efficient.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	N/A	Mention only - never code
2. Using Deque	O(n)	O(n)	No	N/A	Good to code for clarity and efficiency
3. Two Stacks	O(n)	O(n)	No	N/A	Optimal and elegant, great for interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and progressively discuss optimizations. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using level order traversal and reversing alternate levels.Step 3: Discuss the inefficiency of reversing and introduce the deque approach.Step 4: Present the two stacks approach as an optimal solution.Step 5: Code the chosen approach and test with edge cases.

Time Allocation

Clarify: 2min → Approach explanation: 5min → Coding: 10min → Testing & optimization discussion: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of BFS, ability to manipulate data structures to achieve zigzag order, and your coding accuracy and efficiency.

Common Follow-ups

• How would you handle very large trees with limited memory? → Use iterative BFS with streaming output.
• Can you do this traversal using DFS? → Yes, by tracking level and inserting nodes accordingly.

💡 Follow-ups test your flexibility with traversal methods and memory optimization.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree traversal level by level; 2) Output requires alternating order per level; 3) BFS or queue-based traversal is natural; 4) Need to maintain order of nodes per level.

Signature Phrases

zigzag level order traversalalternate direction per levellevel order traversal with reversal

NOT This Pattern When

DFS preorder or inorder traversals, or problems requiring path sums or subtree computations.

Similar Problems

Binary Tree Level Order Traversal - basic level order without zigzagBinary Tree Level Order Traversal II - bottom-up level order traversalN-ary Tree Level Order Traversal - similar BFS pattern for trees with more children

Practice

1. Consider the following code snippet for counting good nodes in a binary tree. Given the tree with root value 3, left child 1 (with left child 3), and right child 4 (with left child 1 and right child 5), what is the final returned count?

easy

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Trace stack operations and count updates

   Start with stack=[(3,3)]. Pop (3,3), count=1. Push right (4,3), left (1,3). Pop (1,3), node.val=1 < 3 no count. Push left (3,3). Pop (3,3), node.val=3 >=3 count=2. Pop (4,3), node.val=4 >=3 count=3. Push right (5,4), left (1,4). Pop (1,4), node.val=1 <4 no count. Pop (5,4), node.val=5 >=4 count=4.

2. Step 2: Final count after traversal

   Count is 4 after visiting all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected good nodes in example [OK]

Hint: Track max_val updates carefully during stack pops [OK]

Common Mistakes:

• Off-by-one counting
• Ignoring max_val update before pushing children
• Mixing left and right child order

2. Consider the following code snippet implementing the optimal recursive approach to connect next pointers in a binary tree. Given the tree below:

       1
      / \
     2   3
    /     \
   4       5

After calling connect(root), what is the value of root.left.right.next?

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

def connect(root):
    if not root:
        return None

    if root.left and root.right:
        root.left.next = root.right

    next_node = root.next
    while next_node:
        if next_node.left:
            next_child = next_node.left
            break
        if next_node.right:
            next_child = next_node.right
            break
        next_node = next_node.next
    else:
        next_child = None

    if root.right:
        root.right.next = next_child
    elif root.left:
        root.left.next = next_child

    connect(root.right)
    connect(root.left)

    return root

easy

A. Node with value 4

B. Node with value 5

C. null

D. Node with value 3

Solution

1. Step 1: Trace connections at root (node 1)

   root.left (2) next -> root.right (3). root.right (3) next -> null (no next at root level).

2. Step 2: Trace connections at node 2

   Node 2 has left child 4, no right child. Its next is 3, which has right child 5. So 4.next -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   4.next points to 5, not null or 3 [OK]

Hint: Next pointers connect nodes across parents at same level [OK]

Common Mistakes:

• Assuming 4.next is null because 2 has no right child
• Confusing next pointers with parent pointers
• Thinking next points to parent or sibling's parent

3. What is the time complexity of the BFS level order traversal approach used to determine if two nodes in a binary tree are cousins, assuming the tree has n nodes?

medium

A. O(n^2) because each level is processed separately

B. O(n log n) due to repeated queue operations

C. O(n) because each node is visited exactly once

D. O(h) where h is the height of the tree due to level traversal

Solution

1. Step 1: Identify BFS traversal cost

   BFS visits each node once, enqueuing and dequeuing each node exactly one time.

2. Step 2: Analyze per-node operations

   Each node's children are checked once, so total operations scale linearly with n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal over all nodes confirms O(n) time [OK]

Hint: BFS visits each node once, so O(n) time [OK]

Common Mistakes:

• Confusing BFS with DFS recursion stack cost
• Assuming repeated level processing causes O(n^2)
• Mistaking height for total nodes

4. What is the time complexity of the optimized BFS approach for checking if a binary tree is symmetric, and why might the common misconception of O(n^2) be incorrect?

medium

A. O(n) because each node is enqueued and dequeued exactly once in pairs

B. O(n) but with O(h) auxiliary space for recursion stack

C. O(n log n) due to repeated subtree comparisons

D. O(n^2) because each node is compared with every other node

Solution

1. Step 1: Identify number of nodes processed

   The BFS approach processes each node exactly once, enqueuing pairs of nodes representing mirrored positions.

2. Step 2: Understand why O(n^2) is incorrect

   There is no nested iteration over all nodes; each node is visited once, so complexity is linear, not quadratic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear traversal of all nodes with pairwise checks yields O(n) time [OK]

Hint: Each node visited once in BFS -> O(n) time [OK]

Common Mistakes:

• Assuming pairwise comparisons multiply to O(n^2)
• Confusing recursion stack space with BFS space
• Thinking repeated subtree checks cause log factor

5. Suppose the problem is extended so that the tree nodes can have multiple children (not just binary), and you need to check if the tree is symmetric around its center. Which modification to the BFS approach is necessary to correctly handle this case?

hard

A. Enqueue children in normal order and compare corresponding children pairs directly

B. Enqueue children in mirrored order and compare pairs from opposite ends of the children list

C. Use a recursive approach only, as BFS cannot handle multiple children

D. Check symmetry only at the root level and ignore deeper levels

Solution

1. Step 1: Understand symmetry in multi-child trees

   Symmetry means the first child on the left subtree mirrors the last child on the right subtree, second mirrors second last, etc.

2. Step 2: Modify BFS to enqueue children in mirrored order

   Enqueue children pairs from opposite ends of the children list to compare mirrored positions correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Mirrored enqueue order for multiple children preserves symmetry checks [OK]

Hint: Multi-child symmetry requires mirrored child pair comparisons [OK]

Common Mistakes:

• Enqueuing children in normal order causing false positives
• Assuming BFS cannot be adapted for multi-child trees
• Ignoring deeper levels of the tree