Connect Nodes at Same Level

Problem Statement

Given a binary tree where each node of the tree holds the following information :

• val
• left pointer
• right pointer
• next pointer

The task required is to connect the node to the next node which is on the same level using the additional next pointer.

Example

Input :

Output :

Explanation :

At the $0^{th}$ level, there is only a single node (root node) so we will connect it to the null pointer (because there is no node on the right side that is at the same level). At the $1^{st}$ level, the nodes are 2, and 3. So, we will connect them like $2\rightarrow 3\rightarrow \text{null}$. At the $2^{nd}$ level, the nodes are 4, 5, 6, and 7. So, we will connect them like $4\rightarrow 5\rightarrow$ $6\rightarrow 7\rightarrow \text{null}$.

Constraints

$0 < n < 10^5$, where $n$ is the number of nodes present in the tree.

Approach 1 : Extend Level Order Traversal or BFS

In the level order traversal of the binary tree, we've seen that by using the queue data structure we can easily traverse in the level order. We can use the same concept to connect nodes at same level by just keeping the track of the previous node encountered in each iteration.

The following steps are required in the algorithm :

• Let the root node of the tree be the root.
• Define a queue data structure (say q) of the node type, and insert the root in it.
• Now iterate till the queue is not empty and do the following :
  • Declare two node type variables, let them be prev and cur.
  • Find the current size of the queue and let it be the size.
  • Iterate from $i = 0$ to $i = size - 1$ and do the following :
    • Assign the front node of the q to the cur, and remove it from the queue.
    • Now, assign cur to prev's next pointer $i.e.$ $prev.next$ = $cur$ if cur is not the leftmost node of the current level, more formally if $i > 0$ holds true.
    • Insert the left and right child of cur in the queue if they are not null.
    • Assign cur to prev.
  • At last, assign null to prev's next pointer. Because it is the last node present at the same level.

Dry Run

Let's dry run this approach on the tree that is given in the example section to connect nodes at the same level :

• Step 1 :
  Initially we will create a queue q and insert the root node in it. So our q will look like this: $q = [1]$ Note that we are using numbers to display the nodes but in reality, the address of nodes will be in the queue.
• Step 2 :
  Iterating till the q is not empty and doing the following things :
  • Iteration 1 :
    After performing the $1^{st}$ iteration, the nodes are linked as $1 \rightarrow \text{null}$ and the q will look like - $q = [2, 3]$.
  • Iteration 2 :
    After performing the $2^{nd}$ iteration, the nodes are linked as $2 \rightarrow 3\rightarrow \text{null}$ and the q will look like : $q = [4, 5, 6, 7]$.
  • Iteration 3 :
    After performing the $3^{rd}$ iteration, the nodes are linked as KaTeX parse error: $ within math mode and the q will look like - $q = [ ]$. Now the queue is empty so we will stop iterating.

Hence, once the dry run is completed we have got our desired result.

Java Implementation

Output :

C++ Implementation

Output :

Python Implementation

Output :

Complexity Analysis

Time Complexity :
As we are traversing the whole binary tree consisting of $n$ nodes. The time complexity will be $O(n)$.

Space Complexity :
Since we have used the queue data structure to store nodes at the next level whose maximum size may reach up to $O(n)$. Therefore, the space complexity is $O(n)$.

Approach 2 : Extend Pre-Order Traversal

In this approach to connect nodes at the same level, we will traverse the tree in the preorder fashion and set the next pointers to make sure that the next pointer of the parent is assigned before its children.

Let's say we are at a node (say node) then we will set the node's left child's next pointer to the node's right child $i.e.$ $node.left.next$ = $node.right$ and we will set node's right child's next pointer to node's next's left child $i.e.$ $node.right.next$ = $node.next.left$.

We can observe that this method will work only on the full binary trees (a binary tree whose nodes have either 2 or 0 children).

The steps involved in the algorithm are as follows :

• The first step is to set the root's next pointer null.
• Then call a recursive function (say connectAtSameLevel) and pass root as the argument.
• In the recursive function, we will have a base condition that will help to handle the null nodes.
• Then, we will check if the node's left pointer is not null then we will assign the $node.right$ pointer to the $node.left.next$ pointer.
• Now, we will check if the right child of the node is not null, then we will assign $node.next.left$ to the $node.right.next$.
• At last, we will recur for the left subtree and then for the right subtree, just like we do in the case of preorder traversal.

Java Implementation

Output :

C++ Implementation

Output :

Python Implementation

Output :

Complexity Analysis

Time Complexity :
We are traversing the whole binary tree once, therefore the overall time complexity to connect nodes at the same level is $O(n)$, where $n$ is the number of nodes present in the tree.

Space Complexity :
Although we are not using any auxiliary data structure, we are using a recursive function so we need to take account of the recursive stack space. Therefore the space complexity is $O(h)$, where $h$ is the height of the tree, and since this method only works on a full binary tree therefore $h \simeq \log_2{n}$.

Why doesn’t Approach-2 Work for Trees which are not Complete Binary Trees ?

As we have discussed earlier that we are doing a pre-order traversal, therefore, we do not know anything about the cousin nodes on the right side, therefore we can't assign the next pointer to the node's right child if the node's next node does not have two children.

Let us understand this through an example of the following binary tree :

Proceeding as per the discussed algorithm :

• Step 1 :
  Assign 1's next node to be null as it is the root node. Also, assign 3 to the next node of 2.
• Step 2 :
  Now, we will recur for the left subtree. So when we will be at node 2, we will assign 5 as the next node of 4. But when we try to find the next node for 5 we can't because 3's left child is not present. Therefore, the algorithm fails here.

Approach 3 : Using NEXT Pointers

In the previous approaches, we are connecting the nodes on the same level on which we are traversing. But in this approach, the idea is to assign the next pointers if level $L + 1$ while being on level $L$.

The steps involved in the algorithm to connect nodes at the same level are as follows :

1. Declare a variable start and assign the address of the root node to it. It will be used to store the address of the leftmost node of the current level.
2. Iterate using the while until the condition $start.left$ $!=$ $null$ holds, and do the following in each iteration :
   • Declare a variable cur and assign the address of start to it. This will be used to traverse the nodes on the current level.
   • Find the first (leftmost) node of the next level and assign its address to start. If there is no further level, then assign null to start.
   • Since, the next level is formed by the left and right children of the current level. So we will iterate the current level and assign values to the next pointer of nodes present in the very next level.
3. When the above while loop is terminated, we will have our task done $i.e.$ connecting the nodes of the next level.

Java Implementation

Output :

C++ Implementation

Output :

Python Implementation

Output :

Complexity Analysis

Time Complexity :
Since we are almost traversing the whole tree (except for the last level), the time complexity is $O(n)$.

Space Complexity :
In this approach neither we are using any auxiliary data structure to perform the task nor we are using any recursive method. Therefore, the overall space complexity is constant $i.e. \text{ } O(1)$.