Populating Next Right Pointers in Each Node

You are given a perfect binary tree, and the task is to populate each ’next’ pointer to point to its next right node. Since it’s a perfect binary tree, every parent node has two children, and all leaves are on the same level.

The algorithm can be implemented using a recursive function. Here’s a step-by-step guide:

Base Case: If the root is null, return immediately as there’s nothing to do.
Connection to Immediate Right: If the root’s left child is not null, connect the root’s left child’s next pointer to the root’s right child.
Connection Across Siblings: If the root’s next pointer is not null, connect the root’s right child’s next pointer to the next pointer of the root’s left child.
Recursion: Call the function recursively for the left and right children of the root.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None

        # Connect immediate right
        if root.left:
            root.left.next = root.right

        # Connect across siblings
        if root.next and root.right:
            root.right.next = root.next.left

        # Recursion on left and right children
        self.connect(root.left)
        self.connect(root.right)

        return root

Key Takeaways:

The recursion follows the pattern of a pre-order traversal (root-left-right).
The time complexity is (O(n)), where (n) is the number of nodes in the tree, since every node is visited once.
The space complexity is (O(\log n)) for the recursion stack since the binary tree is perfect.

Define the Terms perfect binary tree All leaves are on the same level, and every parent has two children.

Define the Interface Input: root Output: root

Analyze the Input and Output

Identify the Invariants

Identify the constraints

The number of nodes in the given tree is less than 4096.
-1000 <= node.val <= 1000

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand

What traversal strategy?
- BFS (Problem requires to create links at every level) [root] [2,3] [4, 5, 6, 7] Can we keep them in a queue? (FIFO)
Establish the next links

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# Definition for Node.
# class Node
#     attr_accessor :val, :left, :right, :next
#     def initialize(val)
#         @val = val
#         @left, @right, @next = nil, nil, nil
#     end
# end

# @param {Node} root
# @return {Node}
def connect(root)
    if root.nil?
        return root
    end
  queue = [root]

  while !queue.empty?
    size = queue.size
    #         keep track of the previous node
    for i in (0...size)
      #      dequeue
      node = queue.shift 

      if i < size - 1
        node.next = queue[0]
      end

      #  we have a perfect binary tree (no need to check node.right)
      if node.left
        # enqueue 
        queue << node.left
      end

      if node.right
        queue << node.right
      end            
    end 
  end
    
  return root
end