Populating Next Right Pointers II (Any Tree)

🎯

Populating Next Right Pointers II (Any Tree)

mediumTREEMicrosoftAmazon

Imagine you have a complex organizational chart where each employee can have any number of direct reports, and you want to connect each employee to their immediate colleague on the right at the same level to facilitate quick lateral communication.

💡 This problem involves connecting nodes at the same level in a binary tree that is not necessarily perfect or complete. Beginners often struggle because unlike perfect trees, you cannot rely on fixed child positions or simple formulas; you must carefully traverse and link nodes level by level.

📋

Problem Statement

Given a binary tree where each node has an additional pointer called 'next', populate each node's next pointer to point to its next right node on the same level. If there is no next right node, the next pointer should be set to NULL. The tree can be any binary tree (not necessarily perfect or complete). You must solve the problem using constant extra space (excluding recursion stack).

The number of nodes in the tree is in the range [0, 10^5].Node values are arbitrary and do not affect the linking.You may only use constant extra space (excluding recursion stack).

💡

Example

Input"root = [1,2,3,4,5,null,7]"

Output[1,#,2,3,#,4,5,7,#]

At level 1, 1's next is NULL. At level 2, 2's next is 3, 3's next is NULL. At level 3, 4's next is 5, 5's next is 7, 7's next is NULL.

• Empty tree → output is NULL
• Tree with only one node → next pointer remains NULL
• Tree where some nodes have only left children → next pointers skip missing right siblings
• Tree where some nodes have only right children → next pointers connect correctly skipping missing left siblings

⚠️

Common Mistakes

Not setting the last node's next pointer to NULL

Leads to incorrect next pointers causing infinite loops or wrong connections

✅ Explicitly set the last node's next pointer in each level to NULL

Using extra space when problem requires constant space

Fails interview constraints or leads to suboptimal solutions

✅ Use the dummy node and next pointers to traverse levels without extra queues

Incorrectly traversing next pointers before they are set

Leads to null pointer exceptions or missing connections

✅ Traverse right child before left child in recursion to ensure next pointers are set

Not handling nodes with only one child properly

Next pointers skip or connect incorrectly

✅ Carefully check for left and right children and connect accordingly

Confusing the dummy node usage and tail pointer updates

Next pointers form incorrect chains or cycles

✅ Always move tail forward after connecting a child

🧠

Brute Force (Level Order Traversal with Extra Queue)

💡 This approach uses a classic BFS with a queue to traverse the tree level by level and connect nodes. It is straightforward and helps beginners understand the problem structure before optimizing space.

Intuition

Traverse the tree level by level using a queue. For each level, connect nodes from left to right by setting their next pointers. Use extra space proportional to the maximum number of nodes at any level.

Algorithm

1. Initialize a queue and enqueue the root node if it exists.
2. While the queue is not empty, process nodes level by level:
3. For each level, iterate through all nodes currently in the queue, linking each node's next pointer to the next node in the queue for that level.
4. Enqueue the children of the current level's nodes for the next iteration.

💡 The challenge is to carefully link nodes within the same level before moving to the next, which is easier with a queue but uses extra memory.

</>

Code

from collections import deque

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
    queue = deque([root])
    while queue:
        size = len(queue)
        prev = None
        for _ in range(size):
            node = queue.popleft()
            if prev:
                prev.next = node
            prev = node
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        prev.next = None
    return root

# Example usage:
# root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(7)))
# connected_root = connect(root)
# print(connected_root.next)  # Should be None since root's next is always None

Line Notes

if not root:Handle empty tree edge case immediately

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

size = len(queue)Determine number of nodes at current level

for _ in range(size):Process all nodes at this level

node = queue.popleft()Get the next node in the current level

if prev:Link previous node's next to current node

prev.next = NoneLast node in level points to None

if node.left:Add left child to queue for next level

if node.right:Add right child to queue for next level

import java.util.*;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node left, Node right, Node next) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node prev = null;
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                if (prev != null) {
                    prev.next = node;
                }
                prev = node;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            prev.next = null;
        }
        return root;
    }

    // Example main to test
    public static void main(String[] args) {
        Node root = new Node(1,
            new Node(2, new Node(4), new Node(5), null),
            new Node(3, null, new Node(7), null),
            null);
        Solution sol = new Solution();
        sol.connect(root);
        System.out.println(root.next); // Should print null since root's next is always null
    }
}

Line Notes

if (root == null) return null;Handle empty tree quickly

Queue<Node> queue = new LinkedList<>();Initialize queue for BFS

queue.offer(root);Start BFS with root node

int size = queue.size();Number of nodes at current level

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

Node node = queue.poll();Get next node in level

if (prev != null) { prev.next = node; }Link previous node's next to current

prev.next = null;Last node in level points to null

if (node.left != null) queue.offer(node.left);Add left child for next level

if (node.right != null) queue.offer(node.right);Add right child for next level

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

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
};

Node* connect(Node* root) {
    if (!root) return nullptr;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        Node* prev = nullptr;
        for (int i = 0; i < size; i++) {
            Node* node = q.front(); q.pop();
            if (prev) prev->next = node;
            prev = node;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        prev->next = nullptr;
    }
    return root;
}

// Example usage
int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(7);
    connect(root);
    cout << (root->next == nullptr ? "null" : "not null") << endl; // Should print null since root's next is always null
    return 0;
}

Line Notes

if (!root) return nullptr;Return immediately if tree is empty

queue<Node*> q;Queue to hold nodes for BFS

q.push(root);Start BFS with root node

int size = q.size();Number of nodes at current level

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

Node* node = q.front(); q.pop();Get next node in current level

if (prev) prev->next = node;Link previous node's next to current

prev->next = nullptr;Last node in level points to nullptr

if (node->left) q.push(node->left);Add left child for next level

if (node->right) q.push(node->right);Add right child for next level

class Node {
    constructor(val, left = null, right = null, next = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

function connect(root) {
    if (!root) return null;
    const queue = [root];
    while (queue.length > 0) {
        let size = queue.length;
        let prev = null;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (prev) prev.next = node;
            prev = node;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        prev.next = null;
    }
    return root;
}

// Example usage:
// const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(7)));
// connect(root);
// console.log(root.next); // Should print null since root's next is always null

Line Notes

if (!root) return null;Handle empty tree edge case

const queue = [root];Initialize queue with root for BFS

let size = queue.length;Number of nodes at current level

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

const node = queue.shift();Dequeue next node in level

if (prev) prev.next = node;Link previous node's next to current

prev.next = null;Last node in level points to null

if (node.left) queue.push(node.left);Add left child for next level

if (node.right) queue.push(node.right);Add right child for next level

⏱

Complexity

TimeO(n)

SpaceO(w) where w is the maximum width of the tree

Each node is visited once, and the queue holds at most the maximum number of nodes at any level.

💡 For a tree with 20 nodes and max width 5, this means about 20 operations and queue size up to 5.

Interview Verdict: Accepted but uses extra space

This approach is easy to understand and implement but does not meet the constant space requirement, so it's a good starting point but not the final solution.

🧠

Better (Using Next Pointers to Traverse Levels)

💡 This approach uses the next pointers themselves to traverse nodes at the current level, avoiding extra queues. It introduces the idea of using a dummy node to build the next level's linked list.

Intuition

Use the already established next pointers to traverse the current level, and build the next level's next pointers on the fly using a dummy node as a placeholder.

Algorithm

1. Initialize a pointer 'current' to the root node.
2. While current is not null, create a dummy node to represent the start of the next level.
3. Use a 'tail' pointer starting at dummy to connect children nodes of the current level.
4. Traverse the current level using next pointers, connecting children to tail and moving tail forward.
5. Move current to dummy.next to process the next level.

💡 The tricky part is managing the dummy and tail pointers to build the next level's linked list without extra space.

</>

Code

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):
    current = root
    while current:
        dummy = Node(0)
        tail = dummy
        while current:
            if current.left:
                tail.next = current.left
                tail = tail.next
            if current.right:
                tail.next = current.right
                tail = tail.next
            current = current.next
        current = dummy.next
    return root

# Example usage:
# root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(7)))
# connected_root = connect(root)
# print(connected_root.next)  # Should be None since root's next is always None

Line Notes

current = rootStart traversal from root

while current:Process each level until no more levels

dummy = Node(0)Dummy node to build next level's linked list

tail = dummyTail pointer to append children

if current.left:Connect left child if exists

tail.next = current.leftLink tail's next to left child

tail = tail.nextMove tail forward

current = current.nextMove to next node in current level

current = dummy.nextMove to first node of next level

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node left, Node right, Node next) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

public class Solution {
    public Node connect(Node root) {
        Node current = root;
        while (current != null) {
            Node dummy = new Node(0);
            Node tail = dummy;
            while (current != null) {
                if (current.left != null) {
                    tail.next = current.left;
                    tail = tail.next;
                }
                if (current.right != null) {
                    tail.next = current.right;
                    tail = tail.next;
                }
                current = current.next;
            }
            current = dummy.next;
        }
        return root;
    }

    // Example main to test
    public static void main(String[] args) {
        Node root = new Node(1,
            new Node(2, new Node(4), new Node(5), null),
            new Node(3, null, new Node(7), null),
            null);
        Solution sol = new Solution();
        sol.connect(root);
        System.out.println(root.next); // Should print null since root's next is always null
    }
}

Line Notes

Node current = root;Start from root node

while (current != null) {Process each level until none left

Node dummy = new Node(0);Dummy node to build next level list

Node tail = dummy;Tail pointer to append children

if (current.left != null) {Connect left child if exists

tail.next = current.left;Link tail's next to left child

tail = tail.next;Move tail forward

current = current.next;Traverse current level using next pointers

current = dummy.next;Move to next level's first node

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
};

Node* connect(Node* root) {
    Node* current = root;
    while (current) {
        Node dummy(0);
        Node* tail = &dummy;
        while (current) {
            if (current->left) {
                tail->next = current->left;
                tail = tail->next;
            }
            if (current->right) {
                tail->next = current->right;
                tail = tail->next;
            }
            current = current->next;
        }
        current = dummy.next;
    }
    return root;
}

// Example usage
int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(7);
    connect(root);
    std::cout << (root->next == nullptr ? "null" : "not null") << std::endl; // Should print null since root's next is always null
    return 0;
}

Line Notes

Node* current = root;Start traversal at root

while (current) {Process each level until none left

Node dummy(0);Dummy node to build next level list

Node* tail = &dummy;Tail pointer to append children

if (current->left) {Connect left child if exists

tail->next = current->left;Link tail's next to left child

tail = tail->next;Move tail forward

current = current->next;Traverse current level using next pointers

current = dummy.next;Move to next level's first node

class Node {
    constructor(val, left = null, right = null, next = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

function connect(root) {
    let current = root;
    while (current) {
        const dummy = new Node(0);
        let tail = dummy;
        while (current) {
            if (current.left) {
                tail.next = current.left;
                tail = tail.next;
            }
            if (current.right) {
                tail.next = current.right;
                tail = tail.next;
            }
            current = current.next;
        }
        current = dummy.next;
    }
    return root;
}

// Example usage:
// const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(7)));
// connect(root);
// console.log(root.next); // Should print null since root's next is always null

Line Notes

let current = root;Start from root node

while (current) {Process each level until none left

const dummy = new Node(0);Dummy node to build next level list

let tail = dummy;Tail pointer to append children

if (current.left) {Connect left child if exists

tail.next = current.left;Link tail's next to left child

tail = tail.next;Move tail forward

current = current.next;Traverse current level using next pointers

current = dummy.next;Move to next level's first node

⏱

Complexity

TimeO(n)

SpaceO(1) extra space

Each node is visited once, and no extra queue is used; only pointers are manipulated.

💡 For 20 nodes, this means about 20 operations and no extra memory beyond a few pointers.

Interview Verdict: Accepted and meets constant space requirement

This approach is optimal for space and time, demonstrating mastery of pointer manipulation in trees.

🧠

Alternative Recursive Approach (Top-Down with Next Pointers)

💡 This recursive approach uses the next pointers to find the next child node at the same level, connecting children recursively. It is elegant but requires careful handling of next pointers.

Intuition

For each node, connect its children and use the node's next pointer to find the next child on the right to connect to. Recursively apply this to all nodes.

Algorithm

1. If the node is null, return.
2. Connect the node's left child to the right child if both exist.
3. Find the next child node on the right by traversing the node's next pointers.
4. Connect the right child or left child to this next child if it exists.
5. Recursively call the function on the right child first, then the left child.

💡 The order of recursion is important to ensure next pointers are set before they are needed.

</>

Code

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

# Example usage:
# root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(7)))
# connected_root = connect(root)
# print(connected_root.next)  # Should be None since root's next is always None

Line Notes

if not root:Base case for recursion

if root.left and root.right:Connect left child to right child if both exist

next_node = root.nextStart searching for next child on the right

while next_node:Traverse next pointers to find next child

if next_node.left:Found next left child to connect

if next_node.right:Found next right child to connect

if root.right:Connect right child to next child if exists

elif root.left:Connect left child to next child if right child missing

connect(root.right)Recurse on right child first to ensure next pointers set

connect(root.left)Recurse on left child after right

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node left, Node right, Node next) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;

        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        }

        Node nextNode = root.next;
        Node nextChild = null;
        while (nextNode != null) {
            if (nextNode.left != null) {
                nextChild = nextNode.left;
                break;
            }
            if (nextNode.right != null) {
                nextChild = nextNode.right;
                break;
            }
            nextNode = nextNode.next;
        }

        if (root.right != null) {
            root.right.next = nextChild;
        } else if (root.left != null) {
            root.left.next = nextChild;
        }

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

        return root;
    }

    // Example main to test
    public static void main(String[] args) {
        Node root = new Node(1,
            new Node(2, new Node(4), new Node(5), null),
            new Node(3, null, new Node(7), null),
            null);
        Solution sol = new Solution();
        sol.connect(root);
        System.out.println(root.next); // Should print null since root's next is always null
    }
}

Line Notes

if (root == null) return null;Base case for recursion

if (root.left != null && root.right != null) {Connect left child to right child if both exist

Node nextNode = root.next;Start searching for next child on right

while (nextNode != null) {Traverse next pointers to find next child

if (nextNode.left != null) {Found next left child to connect

if (nextNode.right != null) {Found next right child to connect

if (root.right != null) {Connect right child to next child if exists

else if (root.left != null) {Connect left child if right child missing

connect(root.right);Recurse on right child first to ensure next pointers set

connect(root.left);Recurse on left child after right

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
};

Node* connect(Node* root) {
    if (!root) return nullptr;

    if (root->left && root->right) {
        root->left->next = root->right;
    }

    Node* nextNode = root->next;
    Node* nextChild = nullptr;
    while (nextNode) {
        if (nextNode->left) {
            nextChild = nextNode->left;
            break;
        }
        if (nextNode->right) {
            nextChild = nextNode->right;
            break;
        }
        nextNode = nextNode->next;
    }

    if (root->right) {
        root->right->next = nextChild;
    } else if (root->left) {
        root->left->next = nextChild;
    }

    connect(root->right);
    connect(root->left);

    return root;
}

// Example usage
int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(7);
    connect(root);
    std::cout << (root->next == nullptr ? "null" : "not null") << std::endl; // Should print null since root's next is always null
    return 0;
}

Line Notes

if (!root) return nullptr;Base case for recursion

if (root->left && root->right) {Connect left child to right child if both exist

Node* nextNode = root->next;Start searching for next child on right

while (nextNode) {Traverse next pointers to find next child

if (nextNode->left) {Found next left child to connect

if (nextNode->right) {Found next right child to connect

if (root->right) {Connect right child to next child if exists

else if (root->left) {Connect left child if right child missing

connect(root->right);Recurse on right child first to ensure next pointers set

connect(root->left);Recurse on left child after right

class Node {
    constructor(val, left = null, right = null, next = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

function connect(root) {
    if (!root) return null;

    if (root.left && root.right) {
        root.left.next = root.right;
    }

    let nextNode = root.next;
    let nextChild = null;
    while (nextNode) {
        if (nextNode.left) {
            nextChild = nextNode.left;
            break;
        }
        if (nextNode.right) {
            nextChild = nextNode.right;
            break;
        }
        nextNode = nextNode.next;
    }

    if (root.right) {
        root.right.next = nextChild;
    } else if (root.left) {
        root.left.next = nextChild;
    }

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

    return root;
}

// Example usage:
// const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(7)));
// connect(root);
// console.log(root.next); // Should print null since root's next is always null

Line Notes

if (!root) return null;Base case for recursion

if (root.left && root.right) {Connect left child to right child if both exist

let nextNode = root.next;Start searching for next child on right

while (nextNode) {Traverse next pointers to find next child

if (nextNode.left) {Found next left child to connect

if (nextNode.right) {Found next right child to connect

if (root.right) {Connect right child to next child if exists

else if (root.left) {Connect left child if right child missing

connect(root.right);Recurse on right child first to ensure next pointers set

connect(root.left);Recurse on left child after right

⏱

Complexity

TimeO(n)

SpaceO(h) recursion stack, h = tree height

Each node is visited once, recursion stack depends on tree height.

💡 For balanced trees with height ~log n, recursion stack is small; for skewed trees it can be up to n.

Interview Verdict: Accepted, elegant but recursion stack may be large

This approach is elegant and uses no extra data structures, but recursion depth can be large for skewed trees, which may be a concern in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the second approach (using next pointers and dummy node) is recommended as it balances clarity and optimal space/time.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Queue BFS)	O(n)	O(w) where w is max width of tree	No	Yes	Mention only - never code due to extra space
2. Optimal (Next Pointers + Dummy Node)	O(n)	O(1) extra space	No	Yes	Code this approach for best results
3. Recursive (Top-Down with Next Pointers)	O(n)	O(h) recursion stack	Yes (skewed trees)	Yes	Mention as alternative, code if comfortable with recursion

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to the optimal approach to impress your interviewer. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints, especially about tree completeness and space requirements.Step 2: Describe the brute force BFS approach using a queue to connect nodes level by level.Step 3: Explain the optimized approach using next pointers and a dummy node to achieve constant space.Step 4: Optionally mention the recursive approach if time permits.Step 5: Code the optimal approach carefully, test with edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of BFS on trees, pointer manipulation, and ability to optimize space from naive to constant. They also check your coding accuracy and handling of edge cases.

Common Follow-ups

• What if the tree is perfect? → You can connect children directly without searching next pointers.
• Can you do this recursively? → Yes, but watch recursion depth and order of calls.
• What if nodes have more than two children? → Extend the dummy-tail approach to connect all children.
• How to verify your connections? → Use level order traversal printing next pointers.

💡 These follow-ups test your flexibility and deeper understanding of the problem and its variants.

🔍

Pattern Recognition

When to Use

1) Need to connect nodes at the same level, 2) Tree is not perfect or complete, 3) Constant extra space required, 4) BFS or level traversal with pointer manipulation

Signature Phrases

'populate each next pointer to the next right node''if there is no next right node, set next pointer to NULL''constant extra space'

NOT This Pattern When

Problems that require only BFS traversal without pointer connections or that allow extra space freely

Similar Problems

Populating Next Right Pointers I - simpler perfect binary tree versionBinary Tree Right Side View - BFS level traversal variantConnect Nodes at Same Level - similar pointer connection problem

Practice

1. Consider the following Python code implementing the optimal DFS approach for bottom-up level order traversal. What is the final output when run on the given tree?

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

def levelOrderBottom(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return levels[::-1]

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(levelOrderBottom(root))

easy

A. [[15, 7], [9, 20], [3]]

B. [[3], [9, 20], [15, 7]]

C. [[9, 20], [3], [15, 7]]

D. [[15, 7], [3], [9, 20]]

Solution

1. Step 1: Trace dfs calls and levels

   Level 0: [3], Level 1: [9, 20], Level 2: [15, 7]

2. Step 2: Reverse levels list before returning

   Reversing [[3], [9, 20], [15, 7]] yields [[15, 7], [9, 20], [3]]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches bottom-up level order traversal [OK]

Hint: Remember to reverse levels collected by DFS [OK]

Common Mistakes:

• Forgetting to reverse levels
• Mixing up left and right children order

2. Consider the following Python code for vertical order traversal of a binary tree:

from collections import deque
from sortedcontainers import SortedDict

def verticalOrder(root):
    if not root:
        return []
    col_table = SortedDict()
    queue = deque([(root, 0)])
    while queue:
        node, col = queue.popleft()
        if col not in col_table:
            col_table[col] = []
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return list(col_table.values())

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

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

What is the output of this code?

easy

A. [[9], [3, 15], [20], [7]]

B. [[9], [3, 20, 15], [7]]

C. [[9], [3], [15, 20], [7]]

D. [[9], [3], [20, 15], [7]]

Solution

1. Step 1: Trace queue and col_table updates

   Start with root (3, col=0). Append 3 to col 0. Enqueue left child (9, col=-1), right child (20, col=1).

2. Step 2: Process nodes in BFS order

   Process (9, -1): append 9 to col -1. No children. Process (20, 1): append 20 to col 1. Enqueue (15, 0), (7, 2). Process (15, 0): append 15 to col 0. Process (7, 2): append 7 to col 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Columns sorted: -1:[9], 0:[3,15], 1:[20], 2:[7] matches [[9], [3, 15], [20], [7]] [OK]

Hint: BFS preserves top-to-bottom order in each column [OK]

Common Mistakes:

• Mixing order of nodes in same column
• Misassigning column indices for children

3. Consider the following BFS-based code snippet for checking if two nodes are cousins in a binary tree. Given the tree below and inputs x=4, y=5, what is the final return value of the function? Tree structure: 1 / \ 2 3 / \ 4 5

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 isCousins(root, x, y):
    if not root:
        return False
    queue = deque([root])
    while queue:
        size = len(queue)
        x_parent = y_parent = None
        for _ in range(size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
                if node.left.val == x:
                    x_parent = node
                if node.left.val == y:
                    y_parent = node
            if node.right:
                queue.append(node.right)
                if node.right.val == x:
                    x_parent = node
                if node.right.val == y:
                    y_parent = node
        if x_parent and y_parent:
            return x_parent != y_parent
        if x_parent or y_parent:
            return False
    return False

easy

A. Raises an exception

B. false

C. null

D. true

Solution

1. Step 1: Trace first level

   Queue starts with root (1). After processing, queue contains nodes 2 and 3. Neither 4 nor 5 found yet.

2. Step 2: Trace second level

   Process nodes 2 and 3. Node 2's left child is 4 (x), so x_parent = 2. Node 3's right child is 5 (y), so y_parent = 3. Both parents found and are different.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nodes 4 and 5 are cousins with different parents at same depth [OK]

Hint: Check parents at same BFS level to confirm cousin status [OK]

Common Mistakes:

• Confusing siblings as cousins
• Returning true if only one parent found
• Not resetting parents each level

4. Suppose the vertical order traversal problem is extended so that nodes can appear multiple times if they have the same column and row but different parents (e.g., in a graph-like structure with shared nodes). Which modification to the BFS with column tracking approach correctly handles this scenario?

hard

A. Modify BFS to track (node, column, row) and store nodes in a list keyed by (column, row), then sort by parent ID

B. Use DFS with sorting by column, row, and parent to order nodes

C. Use BFS with column tracking but ignore row and parent, just append nodes as visited

D. Use BFS with column tracking and a visited set to avoid revisiting nodes

Solution

1. Step 1: Understand problem extension

   Nodes can appear multiple times if they share column and row but differ by parent, so row and parent info must be tracked.

2. Step 2: Evaluate modifications

   Tracking (node, column, row) and sorting by parent ID ensures correct ordering. Ignoring row or parent loses correctness. Visited set prevents duplicates but may skip valid repeats.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracking row and parent allows correct ordering of duplicates [OK]

Hint: Track row and parent to distinguish duplicates in BFS [OK]

Common Mistakes:

• Ignoring row or parent info leads to incorrect grouping
• Using visited set that skips valid repeated nodes

5. Suppose the problem is modified so that the binary tree nodes can be reused multiple times (i.e., the tree can have cycles or repeated references). Which modification to the BFS with indexing approach is necessary to correctly compute the maximum width?

hard

A. Add a visited set to avoid infinite loops and repeated counting of nodes.

B. No modification needed; BFS with indexing works as is.

C. Switch to DFS with memoization to handle repeated nodes.

D. Use a priority queue to process nodes in order of their indices.

Solution

1. Step 1: Understand the impact of node reuse

   Reusing nodes or cycles cause infinite loops in BFS if nodes are revisited repeatedly.

2. Step 2: Modify BFS to track visited nodes

   Adding a visited set prevents revisiting the same node multiple times, avoiding infinite loops and incorrect width calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited set is essential to handle cycles or repeated nodes [OK]

Hint: Use visited set to prevent infinite loops in graphs [OK]

Common Mistakes:

• Assuming tree nodes cannot be reused
• Not adding visited set causing infinite loops
• Switching to DFS unnecessarily