# Solution: Populating Next Right Pointers in Each Node

Let's solve the Populating Next Right Pointers in the Each Node problem using the Tree Breadth-first Search pattern.

## Statement

Given a **perfect binary tree**`next`

. This pointer is initially set to `NULL`

for all nodes. Your task is to connect all nodes of the same hierarchical level by setting the `next`

pointer to its immediate right node.

The `next`

pointer of the rightmost node at each level is set to NULL.

**Constraints:**

- The number of nodes in the tree is in the range $[0, 500]$.
- $-1000 \leq$
`Node.data`

$\leq 1000$

## Solution

So far, youâ€™ve probably brainstormed some approaches and have an idea of how to solve this problem. Letâ€™s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

### Naive approach

The naive approach to establishing connections between nodes at the same level in a binary tree is to utilize a queue data structure and perform a level order traversal. The steps of the algorithm are given below:

- Start with the root node of the binary tree.
- Create an empty queue data structure to perform the breadth-first traversal. Enqueue the root node into the queue.
- While the queue is not empty, perform the following steps:
- Initialize a variable,
`level_size`

, to the current size of the queue (number of nodes in the current level). - Traverse through each node in the current level (equal to
`level_size`

):- Dequeue the front node from the queue and call it the
`current_node`

. - If
`i`

(current index in the level) is less than`level_size - 1`

, set the`next`

pointer of`current_node`

to the first node in the queue (front of the queue) representing the next node at the same level. - Enqueue the left and right children of
`current_node`

(if they exist) into the queue.

- Dequeue the front node from the queue and call it the

- Initialize a variable,
- Return the root node of the modified binary tree with the connections between nodes using the
`next`

pointers.

The time complexity of this naive approach is $O(n)$, where $n$ is the number of nodes in the binary tree. This is because we visit each node once during the breadth-first traversal.

The space complexity of the naive approach is also $O(n)$. At any given time, the queue can store at most one-level nodes in the binary tree. The binary tree is a complete binary tree with $n/2$ nodes in the last level, which is proportional to $n$. Therefore, the space complexity is $O(n)$.

### Optimized approach using Tree Breadth-first Search

To establish connections between nodes at the same level in a binary tree, we can optimize the approach by leveraging the existing tree structure and employing a tree breadth-first search pattern. The goal is to create a linklist-like structure at each level, where each node points to its right sibling.

Instead of using an additional queue data structure, which consumes extra space, we can utilize the existing structure of the binary tree to achieve the same level-order traversal without the need for the queue.

The algorithm uses a nested while loop to traverse the tree and establish the connections:

- First, check if the root node is NULL. If it is, return NULL, indicating an empty tree.
- If the
`root`

is not`NULL`

, it initializes`mostleft`

as the`root`

node. This variable keeps track of the leftmost node of the current level. - Iterate through each level of the tree. The outer loop continues until no more levels are below (
`mostleft.left`

is NULL).

- Inside the outer loop, there is an inner loop that traverses each node on the current level. It starts with the
`current`

variable initialized as the leftmost node of the current level. - Within the inner loop, the algorithm establishes the connections between nodes.
**First connection:**It connects the`current`

nodeâ€™s left child to its right child by assigning`current.left.next`

to`current.right`

.**Second connection:**If there is a next node (`current.next`

) on the same level, it connects the`current`

nodeâ€™s right child to the left child of its next node by assigning`current.right.next`

to`current.next.left`

.- After connecting the nodes on the current level, the
`current`

moves to the next node on the same level. This process continues until the end of the level is reached (`current`

becomes`NULL`

).

- Once the inner loop completes, the
`mostleft`

is updated to the left child of the previous`mostleft`

node. This moves the traversal down to the next level. - The outer loop repeats the above steps until there are no more levels below (
`mostleft.left`

is`NULL`

). - Finally, the modified
`root`

node is returned.

Letâ€™s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.