Populating Next Right Pointers II (Any Tree)

▶

Steps

setup

Start at root node 1

The algorithm begins at the root node with value 1. Since the root is not null, it proceeds to connect its children.

💡 Starting at the root is essential because the algorithm builds connections top-down from the highest level.

Line:

if not root:
    return None

💡 The root node is the entry point for the recursive connection process.

fill_cells

Connect left child 2 to right child 3

Node 1 has both left and right children, so the algorithm sets node 2's next pointer to node 3.

💡 Connecting siblings directly under the same parent is the first step to building horizontal links.

Line:

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

💡 Direct sibling connections are straightforward and form the backbone of the next pointer chain.

compare

Find next child on the right for node 3

The algorithm looks for the next child node to the right of node 1 by traversing node 1's next pointer, which is null, so no next child is found.

💡 Finding the next child on the right is crucial to connect nodes across different parents.

Line:

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

💡 When no next node exists, the next pointer for children on the right edge should be null.

fill_cells

Set right child 3's next pointer to None

Since node 3 is the right child and no next child was found, its next pointer is set to null.

💡 Rightmost nodes at each level should have their next pointer set to null to mark the end of the level.

Line:

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

💡 This step ensures the right boundary of the level is correctly terminated.

traverse

Recurse on right child node 3

The algorithm recursively calls connect on node 3 to set next pointers for its children.

💡 Recursing on the right child first ensures that next pointers are set correctly for nodes on the right side before the left side.

Line:

connect(root.right)

💡 The order of recursion (right before left) is critical for correct next pointer setup.

fill_cells

Node 3 has no left child, skip sibling connection

Node 3 has no left child, so no direct left-to-right child connection is made here.

💡 If a node lacks a left or right child, the algorithm skips direct sibling connection and looks for next children on the right.

Line:

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

💡 Not all nodes have two children; the algorithm handles these cases gracefully.

compare

Find next child on the right for node 7

The algorithm checks node 3's next pointer, which is null, so no next child is found for node 7.

💡 Finding the next child on the right ensures nodes at the same level but different parents are connected.

Line:

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

💡 Node 7 is the rightmost node at its level, so its next pointer should be null.

fill_cells

Set node 7's next pointer to None

Since node 7 is the right child and no next child was found, its next pointer is set to null.

💡 Rightmost nodes at each level have next pointers set to null to mark level boundaries.

Line:

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

💡 This step finalizes the next pointer for node 7 as null.

traverse

Recurse on left child of node 1: node 2

After finishing with node 3, the algorithm recurses on node 2 to connect its children.

💡 Processing the left subtree after the right ensures all next pointers are set correctly from right to left.

Line:

connect(root.left)

💡 The recursion order is right child first, then left child, to maintain correct next pointer setup.

fill_cells

Connect left child 4 to right child 5 of node 2

Node 2 has both left and right children, so node 4's next pointer is set to node 5.

💡 Sibling connections are established first before connecting to neighbors across parents.

Line:

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

💡 Direct sibling connections are the simplest next pointer assignments.

compare

Find next child on the right for node 5

The algorithm traverses node 2's next pointer to find the next child on the right. Node 2's next is node 3, which has a left child null and right child 7, so next_child is node 7.

💡 Connecting nodes across different parents requires traversing next pointers to find the next available child.

Line:

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

💡 The algorithm successfully finds the next child on the right to connect node 5's next pointer.

fill_cells

Set node 5's next pointer to node 7

Since node 5 is the right child and next_child is node 7, node 5's next pointer is set to node 7.

💡 This connection links nodes across different parents at the same level.

Line:

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

💡 Node 5's next pointer now correctly points to node 7, bridging the gap between subtrees.

traverse

Recurse on right child of node 2: node 5

The algorithm recursively calls connect on node 5, which has no children, so it returns immediately.

💡 Leaf nodes have no children to connect, so recursion returns quickly.

Line:

connect(root.right)

💡 Recursion on leaf nodes is a base case that stops further processing.

traverse

Return from node 5, recurse on left child node 4

After finishing node 5, the algorithm recurses on node 4 to connect its children.

💡 Recursing on the left child last completes the processing of the current subtree.

Line:

connect(root.left)

💡 The recursion order ensures all next pointers are set before returning.

traverse

Node 4 has no children, return immediately

Node 4 is a leaf node with no children, so the recursion returns immediately.

💡 Leaf nodes are base cases that end recursion quickly.

Line:

if not root:
    return None

💡 No further connections are needed for leaf nodes.

reconstruct

Return from node 2 and node 1, recursion complete

All recursive calls have completed, and the next pointers for all nodes are set correctly.

💡 The recursion unwinds back to the root, completing the algorithm.

Line:

return root

💡 The entire tree now has next pointers connecting nodes horizontally at each level.

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:
        return None

    # STEP 2: Connect left child to right child if both exist
    if root.left and root.right:
        root.left.next = root.right

    # STEP 3: Find next child on the 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

    # STEP 4: Connect right child or left child to next child
    if root.right:
        root.right.next = next_child
    elif root.left:
        root.left.next = next_child

    # STEP 5: Recurse on right child first
    connect(root.right)
    # STEP 6: Recurse on left child
    connect(root.left)

    # STEP 7: Return root
    return root

📊

Populating Next Right Pointers II (Any Tree) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each node and connection reveals how the next pointers are established top-down, which is difficult to grasp from code alone.

Current node: 1

123457

DFS Stack

1 (entered)

Current node: 1

123457

DFS Stack

1 (entered)root.left.next=3

Current node: 1

123457

DFS Stack

1 (entered)next_node=null next_child=null

Current node: 1

123457

DFS Stack

1 (entered)root.right.next=null

Current node: 3

123457

DFS Stack

3 (entered)1 (right_done)

Current node: 3

123457

DFS Stack

3 (entered)1 (right_done)

Current node: 3

123457

DFS Stack

3 (entered)next_node=null next_child=null1 (right_done)

Current node: 3

123457

DFS Stack

3 (entered)root.right.next=null1 (right_done)

Current node: 2

123457

DFS Stack

2 (entered)1 (returning)

Current node: 2

123457

DFS Stack

2 (entered)root.left.next=51 (returning)root.left.next=5

Current node: 2

123457

DFS Stack

2 (entered)next_node=3 next_child=71 (returning)

Current node: 2

123457

DFS Stack

2 (entered)root.right.next=71 (returning)

Current node: 5

123457

DFS Stack

5 (entered)2 (right_done)1 (returning)

Current node: 4

123457

DFS Stack

4 (entered)2 (right_done)1 (returning)

Current node: 4

123457

DFS Stack

2 (returning)1 (returning)

123457

Return: 1

Key Takeaways

✓ The algorithm connects next pointers top-down, starting from the root and moving level by level.

This top-down approach is hard to see in code but becomes clear when watching the recursion and pointer assignments.

✓ Recursing on the right child before the left child is essential to ensure next pointers are set correctly for nodes on the right side.

The order of recursion affects the availability of next pointers when connecting nodes on the left.

✓ The algorithm handles missing children gracefully by searching the next pointers to find the next available child to connect.

This search across next pointers is a key insight that allows the algorithm to work on any binary tree, not just perfect ones.

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. Given the following code for finding largest values in each tree row, what is the returned list when the input tree is: 1 / \ 3 2 / \ \ 5 3 9

from collections import deque
from typing import Optional, List

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

def largestValues(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_max = float('-inf')
        for _ in range(len(queue)):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level_max)
    return res

easy

A. [1, 3, 5]

B. [1, 3, 9]

C. [1, 5, 9]

D. [1, 2, 9]

Solution

1. Step 1: Trace first level with root node value 1

   Queue initially contains [1]. Max is 1. Append 1 to result.

2. Step 2: Trace second level with nodes 3 and 2

   Queue now [3, 2]. Max is max(3, 2) = 3. Append 3 to result.

3. Step 3: Trace third level with nodes 5, 3, and 9

   Queue now [5, 3, 9]. Max is max(5, 3, 9) = 9. Append 9 to result.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Levels: [1], [3,2], [5,3,9] max values [1,3,9] [OK]

Hint: Track queue size per level to avoid mixing levels [OK]

Common Mistakes:

• Off-by-one in loop causing missing last level
• Mixing nodes from different levels in max calculation
• Incorrect initialization of level_max

3. Consider the following Python code for N-ary tree level order traversal. Given the tree root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)]), what is the value of res after the first iteration of the outer while loop completes?

easy

A. [[1]]

B. [[1, 3, 2, 4]]

C. [[3, 2, 4]]

D. [[5, 6]]

Solution

1. Step 1: Trace the first outer loop iteration

   Initially, current_level contains only the root node with value 1.

2. Step 2: Collect values and enqueue children

   We pop node 1, append its value to level_nodes -> [1], and enqueue its children (3, 2, 4) into next_level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After first iteration, res = [[1]] as only root level processed [OK]

Hint: First level contains only root node value [OK]

Common Mistakes:

• Confusing first level with all children nodes

4. Given the following code snippet implementing the optimal approach to connect next right pointers in a perfect binary tree, what is the value of root.left.next.val after calling connect(root) on the tree Node(1, Node(2), Node(3))?

easy

A. None

B. 2

C. 3

D. 1

Solution

1. Step 1: Trace the first iteration of the outer while loop

   leftmost is root (1), which has left child (2). Inside inner loop, head is 1, so 2.next = 3.

2. Step 2: Check the value of root.left.next

   root.left is node 2, its next pointer is set to node 3, so root.left.next.val = 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   2.next points to 3 after connect [OK]

Hint: Next pointer of left child points to right sibling [OK]

Common Mistakes:

• Confusing node values
• Assuming next is None by default
• Mixing up left and right children

5. The following code attempts to determine if two nodes are cousins in a binary tree using BFS. Identify the line containing the subtle bug that causes incorrect results in some cases.

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 or y_parent:
            return x_parent != y_parent
    return False

medium

A. Line resetting x_parent and y_parent to None at each level

B. Line returning x_parent != y_parent when only one parent is found

C. Line appending children to the queue

D. Line checking if root is null at the start

Solution

1. Step 1: Understand the bug

   The condition 'if x_parent or y_parent:' returns immediately even if only one node is found, which is incorrect.

2. Step 2: Correct logic

   Should return only if both parents are found; otherwise, continue searching or return false after level ends.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Returning on partial discovery causes false positives [OK]

Hint: Return only when both parents found, not one [OK]

Common Mistakes:

• Confusing siblings as cousins
• Not resetting parent pointers each level
• Returning too early when only one node found