117. Populating Next Right Pointers in Each Node II

Level-order traversal using a queue.

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
 
        q = collections.deque([root])
 
        # level-order traversal of the binary tree
        while q:
            # iterate through level, set right pointers
            for i in range(len(q)):
                if i+1 < len(q):
                    print(q[i].val, q[i+1].val)
                    q[i].next = q[i+1]
 
            level_len = len(q)
 
            for _ in range(level_len):
                curnode = q.popleft()
                if curnode.left: q.append(curnode.left)
                if curnode.right: q.append(curnode.right)
        return root

• do a level-order traversal on the binary-tree using bfs and once we complete each level, just go through the array and link the next pointers.

Recursive.

"""
Treat each level as a linked list, and assemble the next pointers
for the level below while iterating through the current level.
"""
class Solution:
    
    def find_next_for_child(self, node):
        curr = node.next
        
        while curr:
            if curr.left:
                return curr.left
            if curr.right:
                return curr.right
            curr = curr.next
            
        return None    
            
    
    def connect(self, root: 'Node') -> 'Node':
        if root:
            if root.right:      
                root.right.next = self.find_next_for_child(root)
                self.connect(root.right)
            if root.left:
                if root.right:
                    root.left.next = root.right
                else:    
                    root.left.next = self.find_next_for_child(root)
                self.connect(root.left)
                
        return root

• find the next node for your children nodes by looking at the next node in the parent’s row.
• only move onto the lower level once it is all connected with next pointers.

117-e1.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

x

null

x

x

cur

x

x

if cur has both left and right child, then cur.left.next = cur.right.

cur.right.next will be the first child node from the left of cur.next (or go to cur.next.next if cur.next has no children)

Link to original

Categories:: binary-tree, tree, dfs, bfs, recursion