deepSWE.io

Populating Next Right Pointers in Each Node

TreesBFS

Problem Statement

You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

Example

Algorithm Explanation

We can solve this problem using a breadth-first search (BFS) approach. We'll traverse the tree level by level, and for each level, we'll connect the nodes from left to right.

Algorithm Steps

Queue: We'll use a queue to perform a level-order traversal. We start by adding the root to the queue.
Level Traversal: While the queue is not empty, we process all nodes at the current level. We can find the number of nodes at the current level by taking the size of the queue.
Connecting Nodes: We iterate through the nodes at the current level. For each node, we dequeue it and set its `next` pointer to the next node in the queue (which is the node to its right). The last node in each level will have its `next` pointer set to `null`.
Enqueue Children: As we process each node, we enqueue its left and right children to be processed in the next level.

Start

Adding root to the queue.

Queue

Populating Next Right Pointers Solution


class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None
        
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.popleft()
                
                if i < level_size - 1:
                    node.next = queue[0]
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
        return root