Populating Next Right Pointers in Each Node

🎯

Populating Next Right Pointers in Each Node

mediumTREEMicrosoftAmazonFacebook

Imagine you are designing a communication system for a perfect binary tree where each node needs to instantly know its immediate right neighbor at the same level to pass messages efficiently.

💡 This problem is about connecting nodes horizontally at the same level in a perfect binary tree. Beginners often struggle because it requires understanding level order traversal and how to link nodes without extra space, which is not straightforward at first.

📋

Problem Statement

Given a perfect binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Input: The root of the perfect binary tree. Output: The same tree with each node's next pointer set to its next right node.

The number of nodes in the tree is in the range [1, 10^5].The tree is perfect: all leaves are on the same level, and every parent has two children.

💡

Example

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

Output[1 -> NULL, 2 -> 3, 3 -> NULL, 4 -> 5, 5 -> 6, 6 -> 7, 7 -> NULL]

At level 1, node 1's next is NULL. At level 2, node 2's next is 3, node 3's next is NULL. At level 3, nodes 4,5,6,7 are connected in order with the last node's next as NULL.

• Single node tree → next pointer remains NULL
• Tree with only two levels → only root's children connected
• Large tree with maximum nodes → performance and memory usage tested
• Null root (empty tree) → should handle gracefully without errors

⚠️

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 to NULL at each level

Using extra space when the problem expects constant space

Suboptimal solution that may be rejected in interviews

✅ Use the next pointers to traverse levels instead of queues

Not handling null or leaf nodes in recursion base case

Causes null pointer exceptions or runtime errors

✅ Add base case checks for null or leaf nodes before recursion

Incorrectly connecting right child's next pointer

Next pointers point to wrong nodes, breaking the chain

✅ Ensure right child's next points to next node's left child if next exists

Confusing level traversal order

Nodes connected in wrong order, failing test cases

✅ Traverse nodes left to right at each level consistently

🧠

Brute Force (Level Order Traversal with Queue)

💡 This approach uses a classic BFS with a queue to connect nodes level by level. It is intuitive and easy to implement but uses extra space proportional to the maximum number of nodes at any level.

Intuition

Traverse the tree level by level using a queue. For each level, connect nodes from left to right by setting their next pointers. The last node in each level points to NULL.

Algorithm

1. Initialize a queue and add the root node.
2. While the queue is not empty, process nodes level by level.
3. For each level, iterate through all nodes and connect each node's next pointer to the next node in the queue for that level.
4. Set the next pointer of the last node in each level to NULL.

💡 The main challenge is to process nodes level by level and connect them correctly, 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:
# Construct tree: 1 -> 2,3 -> 4,5,6,7
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
connect(root)
# After connection, root.next should be None, root.left.next should be root.right
print(root.next)  # None
print(root.left.next.val)  # 3

Line Notes

if not root:Check for empty tree to avoid processing null input

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

while queue:Process nodes level by level until queue is empty

size = len(queue)Number of nodes at current level to separate levels

prev = NoneTrack previous node to connect next pointer

node = queue.popleft()Get current node from queue for processing

if prev:If previous node exists, link its next to current node

prev = nodeUpdate previous node to current for next iteration

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

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

prev.next = NoneLast node in level points to NULL

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, new Node(6), new Node(7), null),
            null);
        Solution sol = new Solution();
        sol.connect(root);
        System.out.println(root.next); // null
        System.out.println(root.left.next.val); // 3
    }
}

Line Notes

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

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

queue.offer(root);Add root node to start BFS

while (!queue.isEmpty()) {Process nodes level by level

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

Node prev = null;Keep track of previous node to link next pointers

Node node = queue.poll();Retrieve current node from queue

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

prev = node;Update previous node

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

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

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

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

class Solution {
public:
    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,
        new Node(2, new Node(4), new Node(5), nullptr),
        new Node(3, new Node(6), new Node(7), nullptr),
        nullptr);
    Solution sol;
    sol.connect(root);
    cout << (root->next == nullptr) << endl; // 1 (true)
    cout << root->left->next->val << endl; // 3
    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

while (!q.empty()) {Process each level until queue is empty

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

Node* prev = nullptr;Track previous node to link next pointers

Node* node = q.front(); q.pop();Get current node from queue

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

prev = node;Update previous node

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

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

class Node {
    constructor(val = 0, 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) {
        const 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, new Node(6), new Node(7)));
connect(root);
console.log(root.next); // null
console.log(root.left.next.val); // 3

Line Notes

if (!root) return null;Handle empty tree input

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

while (queue.length > 0) {Process nodes level by level

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

let prev = null;Track previous node to connect next pointers

const node = queue.shift();Remove node from front of queue

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

prev = node;Update previous node

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

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

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit each node once, so time is O(n). The queue can hold up to the maximum number of nodes at a level, which is O(n/2) = O(n) in worst case.

💡 For n=20 nodes, this means roughly 20 operations and up to 10 nodes in the queue at once.

Interview Verdict: Accepted

This approach works correctly but uses extra memory, which might be a concern for very large trees.

🧠

Optimal (Using Next Pointers to Traverse Levels)

💡 This approach uses the already established next pointers to traverse each level, eliminating the need for extra space. It leverages the perfect binary tree property to connect children nodes efficiently.

Intuition

Start from the leftmost node of each level. Use the next pointers of the current level to connect the children nodes of the next level. Move level by level until all next pointers are set.

Algorithm

1. Initialize a pointer 'leftmost' to the root node.
2. While 'leftmost' has a left child, iterate over the current level using next pointers.
3. For each node in the current level, connect its left child's next to its right child.
4. If the node has a next, connect its right child's next to the next node's left child.
5. Move 'leftmost' down to the leftmost node of the next level and repeat.

💡 The tricky part is using the next pointers to traverse horizontally without extra space and connecting children nodes carefully.

</>

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
    leftmost = root
    while leftmost.left:
        head = leftmost
        while head:
            head.left.next = head.right
            if head.next:
                head.right.next = head.next.left
            head = head.next
        leftmost = leftmost.left
    return root

# Example usage:
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
connect(root)
print(root.left.next.val)  # 3
print(root.left.left.next.val)  # 5

Line Notes

if not root:Handle empty tree edge case

leftmost = rootStart from the root as the leftmost node of the top level

while leftmost.left:Continue until we reach the leaf level (no children)

head = leftmostTraverse nodes horizontally at current level

head.left.next = head.rightConnect left child to right child of same parent

if head.next:If next node exists, connect right child to next node's left child

head = head.nextMove to next node at current level

leftmost = leftmost.leftMove down to the next level's leftmost node

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;
        Node leftmost = root;
        while (leftmost.left != null) {
            Node head = leftmost;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                head = head.next;
            }
            leftmost = leftmost.left;
        }
        return root;
    }

    public static void main(String[] args) {
        Node root = new Node(1,
            new Node(2, new Node(4), new Node(5), null),
            new Node(3, new Node(6), new Node(7), null),
            null);
        Solution sol = new Solution();
        sol.connect(root);
        System.out.println(root.left.next.val); // 3
        System.out.println(root.left.left.next.val); // 5
    }
}

Line Notes

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

Node leftmost = root;Start from root as leftmost node

while (leftmost.left != null) {Traverse levels until leaf level

Node head = leftmost;Traverse nodes horizontally at current level

head.left.next = head.right;Connect left child to right child

if (head.next != null) {If next node exists, connect right child to next node's left child

head.right.next = head.next.left;Link right child to next node's left child

head = head.next;Move to next node at current level

leftmost = leftmost.left;Move down to next level

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

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        Node* leftmost = root;
        while (leftmost->left) {
            Node* head = leftmost;
            while (head) {
                head->left->next = head->right;
                if (head->next) {
                    head->right->next = head->next->left;
                }
                head = head->next;
            }
            leftmost = leftmost->left;
        }
        return root;
    }
};

int main() {
    Node* root = new Node(1,
        new Node(2, new Node(4), new Node(5), nullptr),
        new Node(3, new Node(6), new Node(7), nullptr),
        nullptr);
    Solution sol;
    sol.connect(root);
    std::cout << (root->left->next->val) << std::endl; // 3
    std::cout << (root->left->left->next->val) << std::endl; // 5
    return 0;
}

Line Notes

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

Node* leftmost = root;Start from root as leftmost node

while (leftmost->left) {Traverse levels until leaf level

Node* head = leftmost;Traverse nodes horizontally at current level

head->left->next = head->right;Connect left child to right child

if (head->next) {If next node exists, connect right child to next node's left child

head->right->next = head->next->left;Link right child to next node's left child

head = head->next;Move to next node at current level

leftmost = leftmost->left;Move down to next level

class Node {
    constructor(val = 0, 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;
    let leftmost = root;
    while (leftmost.left) {
        let head = leftmost;
        while (head) {
            head.left.next = head.right;
            if (head.next) {
                head.right.next = head.next.left;
            }
            head = head.next;
        }
        leftmost = leftmost.left;
    }
    return root;
}

// Example usage
const root = new Node(1,
    new Node(2, new Node(4), new Node(5)),
    new Node(3, new Node(6), new Node(7)));
connect(root);
console.log(root.left.next.val); // 3
console.log(root.left.left.next.val); // 5

Line Notes

if (!root) return null;Handle empty tree input

let leftmost = root;Start from root as leftmost node

while (leftmost.left) {Traverse levels until leaf level

let head = leftmost;Traverse nodes horizontally at current level

head.left.next = head.right;Connect left child to right child

if (head.next) {If next node exists, connect right child to next node's left child

head.right.next = head.next.left;Link right child to next node's left child

head = head.next;Move to next node at current level

leftmost = leftmost.left;Move down to next level

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited once, so time is O(n). No extra data structures are used, so space is O(1).

💡 For n=20 nodes, this means about 20 operations and no extra memory beyond variables.

Interview Verdict: Accepted

This is the preferred solution in interviews due to its optimal space usage and clarity.

🧠

Recursive Approach (Top-Down Connection)

💡 This approach uses recursion to connect nodes by passing down the next pointers. It is elegant and leverages the call stack but uses O(h) space where h is tree height.

Intuition

Recursively connect the left child's next to the right child, and the right child's next to the next node's left child if available. Recurse down left and right subtrees.

Algorithm

1. If the current node is null or has no children, return.
2. Connect the left child's next pointer to the right child.
3. If the current node has a next, connect the right child's next pointer to the next node's left child.
4. Recursively call the function on the left and right children.

💡 The recursion implicitly traverses the tree top-down, connecting nodes as it goes.

</>

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 or not root.left:
        return root
    root.left.next = root.right
    if root.next:
        root.right.next = root.next.left
    connect(root.left)
    connect(root.right)
    return root

# Example usage:
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
connect(root)
print(root.left.next.val)  # 3
print(root.left.left.next.val)  # 5

Line Notes

if not root or not root.left:Base case: no node or leaf node reached

root.left.next = root.rightConnect left child to right child

if root.next:If next node exists, connect right child to next node's left child

root.right.next = root.next.leftLink right child to next node's left child

connect(root.left)Recurse on left subtree

connect(root.right)Recurse on right subtree

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 || root.left == null) return root;
        root.left.next = root.right;
        if (root.next != null) {
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
        return root;
    }

    public static void main(String[] args) {
        Node root = new Node(1,
            new Node(2, new Node(4), new Node(5), null),
            new Node(3, new Node(6), new Node(7), null),
            null);
        Solution sol = new Solution();
        sol.connect(root);
        System.out.println(root.left.next.val); // 3
        System.out.println(root.left.left.next.val); // 5
    }
}

Line Notes

if (root == null || root.left == null) return root;Base case: null or leaf node

root.left.next = root.right;Connect left child to right child

if (root.next != null) {If next node exists, connect right child to next node's left child

root.right.next = root.next.left;Link right child to next node's left child

connect(root.left);Recurse on left subtree

connect(root.right);Recurse on right subtree

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

class Solution {
public:
    Node* connect(Node* root) {
        if (!root || !root->left) return root;
        root->left->next = root->right;
        if (root->next) {
            root->right->next = root->next->left;
        }
        connect(root->left);
        connect(root->right);
        return root;
    }
};

int main() {
    Node* root = new Node(1,
        new Node(2, new Node(4), new Node(5), nullptr),
        new Node(3, new Node(6), new Node(7), nullptr),
        nullptr);
    Solution sol;
    sol.connect(root);
    std::cout << root->left->next->val << std::endl; // 3
    std::cout << root->left->left->next->val << std::endl; // 5
    return 0;
}

Line Notes

if (!root || !root->left) return root;Base case: null or leaf node

root->left->next = root->right;Connect left child to right child

if (root->next) {If next node exists, connect right child to next node's left child

root->right->next = root->next->left;Link right child to next node's left child

connect(root->left);Recurse on left subtree

connect(root->right);Recurse on right subtree

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

function connect(root) {
    if (!root || !root.left) return root;
    root.left.next = root.right;
    if (root.next) {
        root.right.next = root.next.left;
    }
    connect(root.left);
    connect(root.right);
    return root;
}

// Example usage
const root = new Node(1,
    new Node(2, new Node(4), new Node(5)),
    new Node(3, new Node(6), new Node(7)));
connect(root);
console.log(root.left.next.val); // 3
console.log(root.left.left.next.val); // 5

Line Notes

if (!root || !root.left) return root;Base case: null or leaf node

root.left.next = root.right;Connect left child to right child

if (root.next) {If next node exists, connect right child to next node's left child

root.right.next = root.next.left;Link right child to next node's left child

connect(root.left);Recurse on left subtree

connect(root.right);Recurse on right subtree

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, so time is O(n). The recursion stack uses O(h) space where h is the tree height.

💡 For a balanced tree with height ~log n, the recursion stack is about log n deep, which is efficient for large n.

Interview Verdict: Accepted

This approach is elegant and accepted but uses recursion stack space, which might be a limitation in very deep trees.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the optimal constant space approach is preferred due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Queue BFS)	O(n)	O(n)	No	N/A	Mention only - easy to explain but not optimal
2. Optimal (Using Next Pointers)	O(n)	O(1)	No	N/A	Code this approach for best results
3. Recursive	O(n)	O(h)	Yes (deep trees)	N/A	Good for explanation, but watch recursion depth

💼

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 finally present the optimal solution. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints, confirm the tree is perfect.Step 2: Describe the brute force BFS approach using a queue.Step 3: Discuss the optimal constant space approach using next pointers.Step 4: Optionally mention the recursive approach for elegance.Step 5: Code the optimal approach and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of BFS, tree traversal, pointer manipulation, and space optimization.

Common Follow-ups

• How to handle trees that are not perfect? → Use a modified approach for imperfect trees.
• Can you do this iteratively without extra space? → Yes, using the next pointers as in the optimal approach.

💡 These follow-ups test your ability to generalize and optimize your solution beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Perfect binary tree given, 2) Need to connect nodes horizontally, 3) Next pointers must be set, 4) Optimize for constant space.

Signature Phrases

'Populate each next pointer to point to its next right node''If there is no next right node, the next pointer should be set to NULL'

NOT This Pattern When

Problems that require vertical connections or arbitrary tree traversals without level linking

Similar Problems

Populating Next Right Pointers in Each Node II - handles imperfect trees with similar logicBinary Tree Right Side View - related to level order traversal and visibilityConnect Nodes at Same Level - similar problem of linking nodes horizontally

Practice

1. Consider the following code snippet for finding the minimum depth of a binary tree using BFS. Given the tree below, what is the value of depth when the first leaf node is dequeued? Tree structure: - Root (1) - Left child (2) - Right child (3) - Left child (4)

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 minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3, TreeNode(4))
print(minDepth(root))

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Trace the BFS queue operations

   Initially queue = [(root(1), 1)]. Dequeue root: not leaf, enqueue left(2,2) and right(3,2).

2. Step 2: Dequeue next node and check leaf

   Dequeue (2,2). Node 2 has no children, so it is a leaf. Return depth = 2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First leaf found at depth 2 -> correct BFS behavior [OK]

Hint: First leaf found at depth 2 in BFS traversal [OK]

Common Mistakes:

• Returning depth 1 because root is counted incorrectly
• Continuing BFS past first leaf node
• Confusing node values with depth

2. Identify the bug in the following code snippet for the right side view of a binary tree:

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.left, depth + 1)  # Line X
        dfs(node.right, depth + 1) # Line Y
    dfs(root, 0)
    return rightside

Which line contains the bug causing incorrect right side view?

medium

A. Line with 'if depth == len(rightside): rightside.append(node.val)'

B. Line X: 'dfs(node.left, depth + 1)'

C. Line Y: 'dfs(node.right, depth + 1)'

D. Line with 'if not node: return'

Solution

1. Step 1: Understand traversal order

   The code visits left child before right child, so left nodes are appended first at each depth.

2. Step 2: Why this causes bug

   Visiting left first causes left nodes to be recorded as visible, overwriting right nodes that should be visible from the right side.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping left and right child calls fixes the bug [OK]

Hint: Right-first DFS needed to capture rightmost nodes [OK]

Common Mistakes:

• Visiting left child before right in DFS causes wrong nodes appended
• Appending nodes without checking depth length
• Not handling null nodes properly

3. The following code attempts to connect next right pointers in any binary tree. Identify the line containing the subtle bug that causes incorrect next pointer connections for nodes with only one child.

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

    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 = null

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

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

    return root

medium

A. Line: if root.left: root.left.next = next_child

B. Line: if root.right: root.right.next = next_child

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

D. Line: connect(root.right)

Solution

1. Step 1: Analyze next pointer assignments

   When both children exist, left.next -> right is set correctly. For single child cases, next_child is found from root.next chain.

2. Step 2: Identify bug in single child handling

   Both if root.right and if root.left set their next to next_child unconditionally. This causes left child to overwrite its next pointer even if right child exists, breaking correct connections.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing if root.left to elif root.left fixes the bug [OK]

Hint: Use elif to avoid overwriting next pointers for left child [OK]

Common Mistakes:

• Setting both left and right child's next unconditionally
• Not breaking after setting left.next when right child exists
• Misordering recursive calls

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 tree nodes can have an arbitrary number of children (not just two). Which of the following approaches correctly extends the optimal recursive solution to connect next right pointers for any number of children per node?

hard

A. Use a depth-first traversal connecting children in reverse order to ensure next pointers are set correctly.

B. Use a queue-based level order traversal to connect all children at each level, as the recursive approach relies on exactly two children.

C. Apply the same recursive approach without changes, as it naturally handles any number of children by connecting left and right pointers.

D. Modify the recursive approach to connect each child to the next child in the node's children list, then connect the last child to the next available child in the next node's children using next pointers.

Solution

1. Step 1: Understand the limitation of the original approach

   The original recursive approach assumes at most two children (left and right) and connects left.next -> right, then right.next -> next child's left or right.

2. Step 2: Extend to arbitrary children

   For multiple children, connect each child to the next child in the list, then connect the last child to the first child of the next node at the same level using next pointers.

3. Step 3: Evaluate options

   Use a queue-based level order traversal to connect all children at each level, as the recursive approach relies on exactly two children. uses extra space (queue), violating optimal constraints. Apply the same recursive approach without changes, as it naturally handles any number of children by connecting left and right pointers. incorrectly assumes the original approach works unchanged. Use a depth-first traversal connecting children in reverse order to ensure next pointers are set correctly.'s reverse order DFS does not guarantee correct next pointer connections across siblings.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Connecting children sequentially and linking last child to next node's first child -> correct extension [OK]

Hint: Connect children sequentially, then link last child to next node's first child [OK]

Common Mistakes:

• Assuming original two-child approach works unchanged
• Using BFS queue despite space constraints
• Connecting children in reverse order