Paras Yadav

Data Structures and Algorithms

Connect Nodes at Same Level

Given a Binary Tree, The task is to connect all the adjacent nodes at the same level starting from the left-most node of that level, and ending at the right-most node

Scope

This article help us know about how to Connect Nodes at Same Level.

In this article we will learn connect nodes using the Extend Level Order Traversal or BFS.

In this article we will learn connect nodes using the Extend Pre-Order Traversal.

In this article we will learn connect nodes Using NEXT Pointers.

Takeaways

Two nodes are considered on the same level if their depth (distance from the root node) is equal.

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 :

      1
     /  \
    /    \
   2      3
  / \    / \
 /   \  /   \
4     5 6    7

Output :

      1 ---------> null
     /  \
    /    \
   2 ---> 3 -----> null
  / \    / \
 /   \  /   \
4 --> 5 6--> 7 --> null

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 $4 \rightarrow 5\rightarrow$$6\rightarrow 7\rightarrow \text{null}$ 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

import java.util.*;

public class Main{

    // Node class
    static class Node{
        int val;
        Node left, right;

        // Adding one additional pointer to
        // keep the address of the next node.
        Node next;

        // Constructor
        Node(int val){
            this.val = val;
            this.left = null;
            this.right = null;
            this.next = null;
        }
    }

    // Function to connect nodes to their next right nodes.
    static void connectAtSameLevel(Node root){
        // Declare the queue.
        Queue<Node> q = new LinkedList<>();
        // Insert root in it.
        q.add(root);

        // Iterate till the queue is not
        // empty.
        while (!q.isEmpty()){
            // Declare two node type variables
            // prev and cur.
            Node prev = null, cur = null;

            // Finding the size of the queue.
            int size = q.size();

            // Iterating from i = 0 to i = size.
            for (int i = 0; i <  size; i++){
                // Assign the front node of the queue
                // to cur.
                cur = q.peek();

                // Remove the front node of the queue.
                q.poll();

                // Assign cur to prev's next pointer
                // if this is not the leftmost node of the level.
                if (i > 0)
                    prev.next = cur;

                // Insert left and right child
                // of cur in queue if they are not null.
                if (cur.left != null)
                    q.add(cur.left);

                if (cur.right != null)
                    q.add(cur.right);

                // Now assign cur to prev.
                prev = cur;
            }

            // Assign null to next pointer
            // of the last node of the current level.
            prev.next = null;
        }

    }
    // Function to print the tree using the next
    // pointer.
    static void printLevelWise(Node root){
        Node cur = root;
        while(cur!=null){
            System.out.print(cur.val + " ---> ");
            cur = cur.next;
        }
        System.out.println("null");

        cur = root.left;
        while(cur!=null){
            System.out.print(cur.val + " ---> ");
            cur = cur.next;
        }
        System.out.println("null");

        cur = root.left.left;
        while(cur!=null){
            System.out.print(cur.val + " ---> ");
            cur = cur.next;
        }
        System.out.println("null");
    }
    // Main function
    public static void main(String[] args) {
        // Constructing the following binary tree.
        //          1
        //         / \
        //        /   \
        //       2     3
        //      / \    / \
        //     /   \  /   \
        //    4    5  6    7
        Node root = new Node(1);
        root.left =  new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        // Calling function to connect nodes
        // at same level.
        connectAtSameLevel(root);

        // Printing the output.
        printLevelWise(root);
    }

}

Output :

1 ---> null
2 ---> 3 ---> null
4 ---> 5 ---> 6 ---> 7 ---> null

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Node class
class Node{
public:
    int val;
    Node *left, *right;

	// Adding one additional pointer to
	// keep the address of the next node.
    Node *next;

    // Constructor
    Node(int Val){
        val = Val;
        left = nullptr;
        right = nullptr;
        next = nullptr;
    }
};

// Function to connect nodes to their next right nodes.
void connectAtSameLevel(Node *root){
    // Declare the queue.
    queue<Node*> q;
    // Insert root in it.
    q.push(root);

    // Iterate till the queue is not
    // empty.
    while (!q.empty()){
        // Declare two node type variables
        // prev and cur.
        Node *prev = nullptr, *cur = nullptr;

        // Finding the size of the queue.
        int size = q.size();

        // Iterating from i = 0 to i = size.
        for (int i = 0; i <  size; i++){
            // Assign the front node of the queue
            // to cur.
            cur = q.front();

            // Remove the front node of the queue.
            q.pop();

            // Assign cur to prev's next pointer
            // if this is not the leftmost node of the level.
            if (i > 0)
                prev->next = cur;

            // Insert left and right child
            // of cur in queue if they are not null.
            if (cur->left != nullptr)
                q.push(cur->left);

            if (cur->right != nullptr)
                q.push(cur->right);

            // Now assign cur to prev.
            prev = cur;
        }

        // Assign null to next pointer
        // of the last node of the current level.
        prev->next = nullptr;
    }

}
// Function to print the tree using the next
// pointer.
void printLevelWise(Node *root){
    Node *cur = root;
    while(cur != nullptr){
        cout << cur->val << " ---> ";
        cur = cur->next;
    }
    cout << "null" << endl;

    cur = root->left;
    while(cur != nullptr){
        cout << cur->val << " ---> ";
        cur = cur->next;
    }
    cout << "null" << endl;

    cur = root->left->left;
    while(cur != nullptr){
        cout << cur->val << " ---> ";
        cur = cur->next;
    }
    cout << "null" << endl;
}
// Main function
int main() {
    // Constructing the following binary tree.
    //          1
    //         / \
    //        /   \
    //       2     3
    //      / \    / \
    //     /   \  /   \
    //    4    5  6    7
    Node *root = new Node(1);
    root->left =  new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // Calling function to connect nodes
    // at same level.
    connectAtSameLevel(root);

    // Printing the output.
    printLevelWise(root);

    return 0;
}

Output :

1 ---> null
2 ---> 3 ---> null
4 ---> 5 ---> 6 ---> 7 ---> null

Python Implementation

# Node class
class Node:
    # Constructor
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        # Adding one additional pointer to
        # keep the address of the next node.
        self.next = None

# Function to connect nodes to their next right nodes.
def connectAtSameLevel(root):
    # Declare the queue.
    q = []
    # Insert root in it.
    q.append(root)

    # Iterate till the queue is not
    # empty.
    while (len(q) > 0):
        # Declare two node type variables
        # prev and cur.
        prev, cur = None, None

        # Finding the size of the queue.
        size = len(q)

        # Iterating from i = 0 to i = size.
        for i in range(size):
            # Assign the front node of the queue
            # to cur.
            cur = q[0]

            # Remove the front node of the queue.
            q.pop(0)

            # Assign cur to prev's next pointer
            # if this is not the leftmost node of the level.
            if (i > 0):
                prev.next = cur

            # Insert left and right child
            # of cur in queue if they are not null.
            if (cur.left != None):
                q.append(cur.left)

            if (cur.right != None):
                q.append(cur.right)

            # Now assign cur to prev.
            prev = cur


        # Assign null to next pointer
        # of the last node of the current level.
        prev.next = None

# Function to print the tree using the next
# pointer.
def printLevelWise(root):
    cur = root
    while(cur != None):
        print(cur.val, " ---> ", end = " ")
        cur = cur.next

    print("null")

    cur = root.left
    while(cur!=None):
        print(cur.val, " ---> ", end = " ")
        cur = cur.next

    print("null")

    cur = root.left.left
    while(cur!=None):
        print(cur.val, " ---> ", end = " ")
        cur = cur.next

    print("null")

# Driver Code

# Constructing the following binary tree.
#          1
#         / \
#        /   \
#       2     3
#      / \    / \
#     /   \  /   \
#    4    5  6    7
root = Node(1)
root.left =  Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

# Calling function to connect nodes
# at the same level.
connectAtSameLevel(root)

# Printing the output.
printLevelWise(root)

Output :

1 ---> null
2 ---> 3 ---> null
4 ---> 5 ---> 6 ---> 7 ---> null

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 :

        1
       / \
      /   \
     2     3
    / \     \
   /   \     \
  4     5     6

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

import java.util.*;

public class Main{

    // Node class
    static class Node{
        int val;
        Node left, right;

        // Adding one additional pointer to
        // keep the address of the next node.
        Node next;

        // Constructor
        Node(int val){
            this.val = val;
            this.left = null;
            this.right = null;
            this.next = null;
        }
    }

    // Function to connect nodes to their next right nodes.
    static void connectAtSameLevel(Node root){
        // Base condition to check if
        // the root itself is null.
        if (root == null)
            return;

        // Declare a variable start and
        // initialize it with the root.
        Node start = root;

        // Iterate while start is not null
        while (start.left != null){
            // Declare a variable cur and
            // initialize it with the start.
            Node cur = start;

            // Iterate while cur is not null
            while (cur != null){
                cur.left.next = cur.right;
                if(cur.next != null)
                    cur.right.next = cur.next.left;

                    cur = cur.next;
            }

            start = start.left;
        }

    }

    // Function to print the tree using the next
    // pointer.
    static void printLevelWise(Node root){
        Node cur = root;
        while(cur!=null){
            System.out.print(cur.val + " ---> ");
            cur = cur.next;
        }
        System.out.println("null");

        cur = root.left;
        while(cur!=null){
            System.out.print(cur.val + " ---> ");
            cur = cur.next;
        }
        System.out.println("null");

        cur = root.left.left;
        while(cur!=null){
            System.out.print(cur.val + " ---> ");
            cur = cur.next;
        }
        System.out.println("null");
    }
    // Main function
    public static void main(String[] args) {
        // Constructing the following binary tree.
        //          1
        //         / \
        //        /   \
        //       2     3
        //      / \    / \
        //     /   \  /   \
        //    4    5  6    7
        Node root = new Node(1);
        root.left =  new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        // Calling function to connect nodes
        // at the same level.
        connectAtSameLevel(root);

        // Printing the output.
        printLevelWise(root);
    }

}

Output :

1 ---> null
2 ---> 3 ---> null
4 ---> 5 ---> 6 ---> 7 ---> null

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Node class
class Node{
public:
    int val;
    Node *left, *right;

    // Adding one additional pointer
    // to keep the address of the next node.
    Node *next;

    // Constructor
    Node(int Val){
        val = Val;
        left = nullptr;
        right = nullptr;
        next = nullptr;
    }
};

// Function to connect nodes to their next right nodes.
void connectAtSameLevel(Node *root){
    // Base condition to check if
    // the root itself is null.
    if (root == nullptr)
        return;

    // Declare a variable start and
    // initialize it with the root.
    Node *start = root;

    // Iterate while start is not null
    while (start->left != nullptr){
        // Declare a variable cur and
        // initialize it with the start.
        Node *cur = start;

        // Iterate while cur is not null
        while (cur != nullptr){
            cur->left->next = cur->right;
            if(cur->next != nullptr)
                cur->right->next = cur->next->left;

                cur = cur->next;
        }

        start = start->left;
    }

}

// Function to print the tree using the next
// pointer.
void printLevelWise(Node *root){
    Node *cur = root;
    while(cur != nullptr){
        cout << cur->val << " ---> ";
        cur = cur->next;
    }
    cout << "null" << endl;

    cur = root->left;
    while(cur != nullptr){
        cout << cur->val << " ---> ";
        cur = cur->next;
    }
    cout << "null" << endl;

    cur = root->left->left;
    while(cur != nullptr){
        cout << cur->val << " ---> ";
        cur = cur->next;
    }
    cout << "null" << endl;
}
// Main function
int main() {
    // Constructing the following binary tree.
    //          1
    //         / \
    //        /   \
    //       2     3
    //      / \    / \
    //     /   \  /   \
    //    4    5  6    7
    Node *root = new Node(1);
    root->left =  new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // Calling function to connect nodes
    // at same level.
    connectAtSameLevel(root);

    // Printing the output.
    printLevelWise(root);

    return 0;
}

Output :

1 ---> null
2 ---> 3 ---> null
4 ---> 5 ---> 6 ---> 7 ---> null

Python Implementation

# Node class
class Node:
    # Constructor
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        # Adding one additional pointer
        # to keep the address of the next node.
        self.next = None

# Function to connect nodes to their next right nodes.
def connectAtSameLevel(root):
    # Base condition to check if
    # the root itself is null.
    if (root == None):
        return

    # Declare a variable start and
    # initialize it with the root.
    start = root

    # Iterate while start is not null
    while (start.left != None):
        # Declare a variable cur and
        # initialize it with the start.
        cur = start

        # Iterate while cur is not null
        while (cur != None):
            cur.left.next = cur.right
            if(cur.next != None):
                cur.right.next = cur.next.left

            cur = cur.next

        start = start.left

# Function to print the tree using the next
# pointer.
def printLevelWise(root):
    cur = root
    while(cur != None):
        print(cur.val, " ---> ", end = " ")
        cur = cur.next

    print("null")

    cur = root.left
    while(cur!=None):
        print(cur.val, " ---> ", end = " ")
        cur = cur.next

    print("null")

    cur = root.left.left
    while(cur!=None):
        print(cur.val, " ---> ", end = " ")
        cur = cur.next

    print("null")

# Driver Code

# Constructing the following binary tree.
#          1
#         / \
#        /   \
#       2     3
#      / \    / \
#     /   \  /   \
#    4    5  6    7
root = Node(1)
root.left =  Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

# Calling function to connect nodes
# at the same level.
connectAtSameLevel(root)

# Printing the output.
printLevelWise(root)

Output :

1 ---> null
2 ---> 3 ---> null
4 ---> 5 ---> 6 ---> 7 ---> null

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. O(1).

Conclusion

  • All the nodes on the same level are connected using an additional next pointer (similar to a linked list).
  • A modified version of level order traversal can be implemented to connect nodes with the nodes at the same level.
  • An algorithm using the pre-order traversal also exists, but it is limited because it works only for complete binary trees.
  • Connecting nodes can be very helpful in certain scenarios where we just need nodes present on a given level.
  • For example, if we want to get the list of folders present inside some kk directories then this method can be useful.

Author

Latest articles

Largest Number Formed from an Array

Sindhuja Gudala

Fundamentals of Enhanced Interior Gateway Routing Protocol

Trapti Gupta

What is Network Hub?

Akshay Mishra