deepSWE.io

Populating Next Right Pointers in Each Node II

TreesBFS

Problem Statement

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`.

Initially, all `next` pointers are set to `NULL`. You may only use constant extra space.

Example

The key to solving this problem is to use a level-order traversal approach. Since we need to connect nodes at the same level, processing the tree level by level is a natural fit. We can't use a simple queue-based BFS like in the first version of this problem because we need to handle the connections between levels.

A more robust approach is to use a "dummy head" for each level. We iterate through the current level using the `next` pointers we've already established. As we traverse the current level, we build the `next` pointers for the level below it.

Algorithm Steps

Initialize a `root` pointer, which will be the start of the current level we are processing.
Create a `dummy` node to act as the head of the next level. A `tail` pointer will help us build the next level.
Loop as long as `root` is not null (i.e., there are more levels to process).
Inside the loop, iterate through the current level using the `root` pointer and its `next` connections.
For each node in the current level, check if it has left and/or right children.
If a child exists, connect the `tail`'s `next` pointer to it and then advance the `tail` pointer.
After iterating through all nodes in the current level, the `dummy.next` pointer will be the head of the next level. Set `root` to `dummy.next` to process the next level.
Reset the `dummy` and `tail` pointers for the next iteration.

Start

Starting with the root node.

Code Example


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

        level_head = root
        while level_head:
            dummy = Node(0)
            tail = dummy
            
            current = level_head
            while current:
                if current.left:
                    tail.next = current.left
                    tail = tail.next
                if current.right:
                    tail.next = current.right
                    tail = tail.next
                current = current.next
            
            level_head = dummy.next
            
        return root