Populating Next Right Pointers in Each Node II

One way to solve this problem is to perform a level-order traversal (BFS) and connect nodes within the same level. Here’s the step-by-step guide:

  1. Initialization: Initialize a queue and add the root node if it’s not null.
  2. Level Traversal: Iterate through the levels of the tree by using a loop inside which you handle each level separately.
  3. Node Connections: For each level, connect all nodes from left to right by iterating through the nodes of that level and setting the next pointer.
  4. Next Level: Add the left and right children of the nodes to the queue, if they are not null, to handle the next level in the following iteration.
 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

from collections import deque

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None

        # Initialize the queue with the root
        queue = deque([root])

        while queue:
            level_size = len(queue)

            # Iterate through the current level
            for i in range(level_size):
                node = queue.popleft()

                # Connect the current node to the next node in the same level
                if i < level_size - 1:
                    node.next = queue[0]

                # Add the left and right children to the queue
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return root

Key Takeaways:

  • The solution makes use of a queue to facilitate level-order traversal.
  • 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(w)), where (w) is the maximum width of the tree (maximum number of nodes at any level), since this many nodes can be in the queue at once.
 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

class Solution:
    def processChild(self, childNode, prev, leftmost):
        if childNode:            
            if prev:
                prev.next = childNode
            else:    
                leftmost = childNode
            prev = childNode 
        return prev, leftmost

    def connect(self, root: 'Node') -> 'Node':        
        if not root:
            return root

        leftmost = root

        while leftmost:            
            prev, curr = None, leftmost            
            leftmost = None

            while curr:                
                prev, leftmost = self.processChild(curr.left, prev, leftmost)
                prev, leftmost = self.processChild(curr.right, prev, leftmost)

                curr = curr.next

        return root 

 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
43
44

# Definition for a Node.
# class Node
#     attr_accessor :val, :left, :right, :next
#     def initialize(val)
#         @val = val
#         @left, @right, @next = nil, nil, nil
#     end
# end

def process_child(child, previous, head)
  if child
      if previous
          previous.next = child
      else
          head = child
      end
      previous = child
  end

   [previous, head]       
end

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

    head = root

    while head
       previous, current = nil, head
       head = nil

        while current
           previous, head = process_child(current.left, previous, head)
           previous, head = process_child(current.right, previous, head) 

           current = current.next
        end
    end
    root
end