Solution: Populating Next Right Pointers in Each Node

Statement

Given a perfect binary treeA binary tree in which all the levels are completely filled with nodes, and all leaf nodes (nodes with no children) are at the same level., where each node contains an additional pointer called 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:

1. Start with the root node of the binary tree.
2. Create an empty queue data structure to perform the breadth-first traversal. Enqueue the root node into the queue.
3. While the queue is not empty, perform the following steps:
   • Initialize a variable, levelSize, to the current size of the queue (number of nodes in the current level).
   • Traverse through each node in the current level (equal to levelSize):
     • Dequeue the front node from the queue and call it the currentNode.
     • If i (current index in the level) is less than levelSize - 1, set the next pointer of currentNode 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 currentNode (if they exist) into the queue.
4. 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:

1. First, check if the root node is NULL. If it is, return NULL, indicating an empty tree.
2. 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.
3. 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).

7. 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.
8. The outer loop repeats the above steps until there are no more levels below (mostleft.left is NULL).
9. Finally, the modified root node is returned.

Let’s look at the following illustration to get a better understanding of the solution: