Populating Next Right Pointers in Each Node

▶

Steps

setup

Start at root node 1

The algorithm begins at the root node (value 1). It checks if the node is null or has no children to decide if it should return immediately.

💡 This step sets the base condition for recursion and starts the process at the top of the tree.

Line:

if not root or not root.left:
    return root

💡 The root node is the entry point; recursion will proceed only if children exist.

fill_cells

Connect left child 2's next to right child 3

The algorithm sets node 2's next pointer to node 3, connecting siblings at the second level.

💡 Connecting siblings at the same parent level is the core operation to build horizontal links.

Line:

root.left.next = root.right

💡 Left child's next pointer is always the right child of the same parent.

fill_cells

Connect right child 3's next to null (no next for root)

Since node 1 has no next, node 3's next pointer remains null, marking the end of the second level.

💡 The rightmost node at each level always points to null, indicating no further nodes on that level.

Line:

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

💡 Right child's next pointer depends on parent's next pointer; if none, it stays null.

traverse

Recurse on left child node 2

The algorithm recursively calls connect on node 2 to connect its children and their next pointers.

💡 Recursion dives into the left subtree to apply the same connection logic at the next level.

Line:

connect(root.left)

💡 Recursion ensures all levels are processed top-down, left subtree first.

fill_cells

Connect left child 4's next to right child 5

At node 2, connect its left child 4's next pointer to its right child 5.

💡 Sibling connections are repeated at each subtree level.

Line:

root.left.next = root.right

💡 The pattern of connecting left child's next to right child is consistent at every node with children.

fill_cells

Connect right child 5's next to node 3's left child 6

Since node 2 has a next (node 3), connect node 5's next pointer to node 3's left child 6, linking nodes across parents.

💡 This step connects nodes horizontally across different parents, completing the level linkage.

Line:

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

💡 Next pointers enable linking nodes across sibling subtrees, not just within the same parent.

traverse

Recurse on left child node 4 (leaf)

The algorithm calls connect on node 4, which is a leaf node with no children, so it returns immediately.

💡 Leaf nodes stop recursion, preventing unnecessary calls.

Line:

if not root or not root.left:
    return root

💡 Base case of recursion ensures termination at leaves.

traverse

Recurse on right child node 5 (leaf)

The algorithm calls connect on node 5, another leaf node, which returns immediately.

💡 Leaves are base cases for recursion, ensuring no further processing.

Line:

if not root or not root.left:
    return root

💡 Leaves do not have next pointers to set, so recursion ends here.

returning

Return from node 2 recursion

After processing both children, the recursion returns from node 2 back to node 1.

💡 Returning from recursion unwinds the call stack to continue processing other subtrees.

Line:

return root

💡 Recursion completes for left subtree before moving to right subtree.

traverse

Recurse on right child node 3

The algorithm now processes the right subtree by calling connect on node 3.

💡 Recursion proceeds to the right subtree after completing the left subtree.

Line:

connect(root.right)

💡 The algorithm processes all nodes by recursively traversing left then right children.

fill_cells

Connect left child 6's next to right child 7

At node 3, connect its left child 6's next pointer to its right child 7.

💡 Sibling connections continue at the right subtree.

Line:

root.left.next = root.right

💡 The sibling connection rule applies uniformly across the tree.

fill_cells

Connect right child 7's next to null (no next for node 3)

Node 3 has no next, so node 7's next pointer remains null, marking the end of the third level.

💡 Rightmost nodes at each level always point to null.

Line:

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

💡 Next pointers terminate at the rightmost node of each level.

traverse

Recurse on left child node 6 (leaf)

The algorithm calls connect on node 6, a leaf node, which returns immediately.

💡 Leaves stop recursion to prevent unnecessary calls.

Line:

if not root or not root.left:
    return root

💡 Base case ensures recursion ends at leaves.

traverse

Recurse on right child node 7 (leaf)

The algorithm calls connect on node 7, a leaf node, which returns immediately.

💡 Leaves are base cases that stop recursion.

Line:

if not root or not root.left:
    return root

💡 Leaves do not require next pointer connections.

returning

Return from node 3 recursion

After processing both children, recursion returns from node 3 back to node 1.

💡 Recursion unwinds after completing right subtree.

Line:

return root

💡 Recursion completes for right subtree after left subtree is done.

returning

Return from root node 1 recursion

After processing both left and right subtrees, recursion returns from root node 1, completing the algorithm.

💡 Final return provides the fully connected tree.

Line:

return root

💡 The entire tree now has next pointers populated correctly.

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):
    # STEP 1: Base case check
    if not root or not root.left:
        return root
    # STEP 2: Connect left child next to right child
    root.left.next = root.right
    # STEP 3: Connect right child next to next node's left child if exists
    if root.next:
        root.right.next = root.next.left
    # STEP 4: Recurse on left child
    connect(root.left)
    # STEP 5: Recurse on right child
    connect(root.right)
    # STEP 6: Return root after connections
    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

📊

Populating Next Right Pointers in Each Node - Watch the Algorithm Execute, Step by Step

Watching each connection and recursive call helps you understand how the algorithm efficiently links nodes without extra space, which is hard to grasp from code alone.

Current node: 1

1234567

DFS Stack

1 (entered)

Current node: 1

1234567

DFS Stack

1 (entered)

Current node: 1

1234567

DFS Stack

1 (entered)

Current node: 2

1234567

DFS Stack

2 (entered)1 (entered)

Current node: 2

1234567

DFS Stack

2 (entered)1 (entered)

Current node: 2

1234567

DFS Stack

2 (entered)1 (entered)

Current node: 4

1234567

DFS Stack

4 (entered)2 (entered)1 (entered)

Return: 4

Current node: 5

1234567

DFS Stack

5 (entered)2 (entered)1 (entered)

Return: 5

Current node: 2

1234567

DFS Stack

1 (entered)

Return: 2

Current node: 3

1234567

DFS Stack

3 (entered)1 (entered)

Current node: 3

1234567

DFS Stack

3 (entered)1 (entered)

Current node: 3

1234567

DFS Stack

3 (entered)1 (entered)

Current node: 6

1234567

DFS Stack

6 (entered)3 (entered)1 (entered)

Return: 6

Current node: 7

1234567

DFS Stack

7 (entered)3 (entered)1 (entered)

Return: 7

Current node: 3

1234567

DFS Stack

1 (entered)

Return: 3

Current node: 1

1234567

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

Return: 1

Key Takeaways

✓ The algorithm connects nodes level by level using recursion without extra space.

This insight is hard to see from code alone because the recursion and pointer assignments are intertwined.

✓ Sibling nodes are connected first, then connections across parents are made using the parent's next pointer.

Visualizing this clarifies how horizontal links span beyond immediate siblings.

✓ Recursion terminates at leaf nodes, ensuring efficient traversal without redundant calls.

Seeing the base case in action helps understand recursion depth and termination.

Practice

1. Given a binary tree and two node values, you need to determine if these nodes are at the same depth but have different parents. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Breadth-first search (BFS) level order traversal to check nodes level by level

B. Dynamic programming to store subtree information and compare nodes

C. Depth-first search (DFS) separately to find depth and parent of each node

D. Greedy approach to pick nodes based on immediate parent comparison

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if two nodes are at the same depth and have different parents, which naturally aligns with level-based traversal.

2. Step 2: Identify algorithm suitability

   BFS level order traversal processes nodes level by level, allowing simultaneous checking of node parents and depths in O(n) time, making it optimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS directly accesses nodes by level, perfect for cousin checks [OK]

Hint: Level order traversal matches level-based cousin checks [OK]

Common Mistakes:

• Using DFS twice separately wastes time
• Greedy misses depth checks
• DP is unnecessary overhead

2. You need to find the value of the leftmost node at the deepest level of a binary tree. Which approach guarantees an optimal solution that efficiently finds this value without traversing unnecessary nodes multiple times?

easy

A. Breadth-first search (BFS) level order traversal inserting right child before left child to ensure the last node processed is the bottom-left node.

B. Depth-first search (DFS) that tracks the maximum depth and updates the leftmost node when a deeper level is found.

C. Greedy traversal always choosing the left child first until reaching the deepest node.

D. Dynamic programming storing results of subtrees to combine leftmost values at each depth.

Solution

1. Step 1: Understand problem goal

   The problem requires finding the bottom-left value, which is the leftmost node at the deepest level.

2. Step 2: Analyze BFS approach with right-to-left insertion

   BFS with queue inserting right child before left child ensures the last node popped is the bottom-left node, but this approach requires careful enqueue order and may be less intuitive.

3. Step 3: Analyze DFS approach

   DFS that tracks maximum depth and updates the leftmost node when a deeper level is found directly finds the bottom-left node efficiently without relying on enqueue order.

4. Step 4: Choose optimal approach

   DFS approach is simpler and guarantees correct bottom-left node without tricky enqueue order.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   DFS tracking max depth and leftmost node is a standard, efficient solution [OK]

Hint: DFS tracking max depth and leftmost node efficiently finds bottom-left node [OK]

Common Mistakes:

• Assuming BFS with right-to-left insertion is always simpler
• Thinking greedy left child traversal always finds bottom-left
• Misapplying DP to this problem

3. 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

4. Identify the bug in the following code snippet that attempts to find the bottom-left tree value using BFS:

from collections import deque

class Solution:
    def findBottomLeftValue(self, root):
        queue = deque([root])
        node = None
        while queue:
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return node.val

What is the bug in this code?

medium

A. Appending left child before right child causes the last node to be the bottom-right, not bottom-left.

B. Not initializing node before the loop causes a runtime error if root is None.

C. Returning node.val instead of queue[-1].val returns the wrong node value.

D. Using deque instead of list causes inefficient queue operations.

Solution

1. Step 1: Analyze enqueue order

   The code enqueues left child before right child, so BFS processes nodes left to right at each level.

2. Step 2: Identify last node popped

   Because left child is enqueued first, the last node popped is the bottom-right node, not bottom-left.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Right-to-left insertion is needed to get bottom-left node last [OK]

Hint: Order of child insertion in BFS affects which node is last popped [OK]

Common Mistakes:

• Assuming left-first enqueue gives bottom-left node
• Confusing last popped node with first node at last level
• Thinking deque is inefficient for BFS

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