Skip to main content

Populating Next Right Pointers in Each Node II

Question​

Given a binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. The tree has a special structure, where the leftmost node in the level is the last node of the previous level.

How can we populate each next pointer to point to its next right node in a binary tree with this special structure?

Example 1
None

Solution​

all//Populating Next Right Pointers in Each Node II.py


# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

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

        # Start with the root node. There are no next pointers
        # that need to be set up on the first level
        leftmost = root

        # Once we reach the final level, we are done
        while leftmost.left:
            # Iterate the "linked list" starting from the head
            # node and using the next pointers, establish the
            # corresponding links for the next level
            head = leftmost

            while head:
                # CONNECTION 1
                head.left.next = head.right

                # CONNECTION 2
                if head.next:
                    head.right.next = head.next.left

                # Progress along the list (nodes on the current level)
                head = head.next

            # Move onto the next level
            leftmost = leftmost.left

        return root