Hello ninjas! Remember your peers' last interview? Did they get stuck in this famous Data structure problem? Don't worry. You are a ninja! Read with us, and we will ensure that these kinds of problems will not act as a barrier between you and a great product-based company.

This blog will solve all your headaches regarding the problem of populating the inorder Successor for all nodes, but before that, there are certain things that you should be aware of. It includes Inorder traversal, so let us begin this article with the basic overview of Inorder traversal.

Inorder traversal

The tree data structures are nonlinear in nature, and this enables them to be traversed in multiple ways. These numerous ways include Inorder traversal as one of the most used traversal methods. In this method, we traverse through the left children first, followed by the root node and, at last, the right children. We use a queue to store the element and display it whenever required.

In the following image the inorder traversal will be in the given order 5 -> 2 -> 7. As they are left, root, and the right node.

Let us now move on to the exact problem statement in the next section.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Problem statement

For a given binary tree and the next pointer of a specified structure, we need to define a function that will populate the next pointer for all nodes here. The catch is that the next pointer should point to the inorder Successor of the given node. Now the question arises what the inorder Successor for a given node is? It is nothing but the next element which was to be traversed in the case of inorder traversal. For example, if we are on the left node, then the inorder Successor will be the root node. Similarly, for the root node, it will be the left node.

I hope we have made the problem statement clear to you. Let us now see the structure of the next pointer.

Now moving forward to the next step, where we will be discussing its solution.

Solution

We will be discussing two approaches to this problem

1st Approach(Using reverse inorder traversal)

Here we will be using the reverse inorder traversal method. In this method, we will traverse the binary tree in reverse order, and then we will put the last visited element to the next of the number. This will populate the next pointer pointing to the inorder Successor of the current node.

Looking at the Approach without the actual implementation and algorithm is like accessing a laptop without an internet connection 😂😂. Don't worry. We would not do that to you! So here is the algorithm for the 1st Approach.

Algorithm

Step 1 - Start Step 2 - Create a function named populateNext Step 3 - Start traversing the node in reverse order(right node first) Step 4 - Set the next pointer in the right subtree Step 5 - Set the next as previously visited node in reverse order Step 6 - Update the previous node for the subsequent node Step 7 - Set the next pointer to the left subtree Step 8 - Will create a Helper function named as newnode to allocate null to the left and right subtreee Step 9 - Create the main function to execute Step 10 - Stop.

Code

// A program in C++ to populate in order successor
// traversal of all nodes in a tree
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node* next;
};
//Traversing the tree in reverse in order traversal and setting the next of P
void populateNext(node* p)
{
//We will traverse the rightmost node first
//The next pointer to the rightmost node will be null
if (p) {
// Firstly we will set the next pointer in the right subtree
populateNext(p->right);
// Setting the next as previously visited node in reverse Inorder
p->next = next;
// Change the previous for the subsequent node
next = p;
// Finally, setting the next pointer in left subtree
populateNext(p->left);
}
}
/* Helper function that allocates a new
node with the given data and NULL to the left
and right pointers. */
node* newnode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
Node->next = NULL;
return (Node);
}
// Driver Code to execute the program
int main()
{
node* root = newnode(11);
root->left = newnode(9);
root->right = newnode(13);
root->left->left = newnode(4);
populateNext(root);
// Displaying the populated values
node* ptr = root->left->left;
while (ptr) {
// -1 is printed if there is no successor
cout << "Next of " << ptr->data << " is "
<< (ptr->next ? ptr->next->data : -1) << endl;
ptr = ptr->next;
}
return 0;
}

Now let us look at the output of the above code

Output

2nd Approach(Using stack)

In this, we will be using the stack to populate in order successor for all nodes.

To keep all the left elements belonging to a node until the node is the leftmost node itself, we will be using a stack. Then, in the stack, we will save everything to the left of the right of the leftmost node. Then, until the stack is empty, point the current node's next element to the topmost element of the stack, and if the topmost element of the node has a right node, store all the left elements on the right of the topmost. Let us see its algorithm

Algorithm

Step 1 - Start Step 2 - Create a stack Step 3 - Create a temp variable which will point to root node Step 4 - Push temp into our stack Step 5 - Update the value of temp to temp -> left Step 6 - Repeat step 4 and 5 until temp is null. Step 7 - Create a curr variable pointing to temp Step 8 - Check if curr.right is empty. Step 9 - If not empty then push all the left nodes into the stack Step 10 - Do an inorder traversal present in our stack Step 11 - Execute the main function Step 11 - Exit

Let us see its implementation.

Code

//A c++ program to populate inorder successor for all nodes using a stack
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
struct Node* left;
struct Node* right;
struct Node* next;
Node(int y)
{
data = y;
left = NULL;
right = NULL;
next = NULL;
}
};
Node* inorder(Node* root)
{
if (root->left == NULL)
return root;
inorder(root->left);
}
void populateNext(Node* root)
{
stack<Node*> stck;
Node* temp = root;
while (temp->left) {
stck.push(temp);
temp = temp->left;
}
Node* curr = temp;
if (curr->right) {
Node* q = curr->right;
while (q) {
stck.push(q);
q = q->left;
}
}
while (!stck.empty()) {
Node* inorder = stck.top();
stck.pop();
curr->next = inorder;
if (inorder->right) {
Node* q = inorder->right;
while (q) {
stck.push(q);
q = q->left;
}
}
curr = inorder;
}
}
Node* newnode(int data)
{
Node* node = new Node(data);
return (node);
}
int main()
{
Node* root = newnode(12);
root->left = newnode(9);
root->right = newnode(11);
root->left->left = newnode(4);
populateNext(root);
Node* ptr = inorder(root);
while (ptr) {
// We will print -1 if there is no successor
cout << "Next of " << ptr->data << " is "
<< (ptr->next ? ptr->next->data : -1) << endl;
ptr = ptr->next;
}
return 0;
}

Now let us look at its output

Output

With this, we come to the end of the blog, and I hope you found it interesting and insightful. Let us now discuss some of the Frequently asked questions related to this.

The inorder traversal is a kind of traversal that traverses in left node->root node->right node order.

How many types of traversal are there?

The tree data structure has four types of traversal methods. Inorder, Pre-order, Post-order, and Level-order are their names.

What do you mean by Inorder Successor?

The Inorder Successor is the next element which is to be traversed in the inorder traversal.

For example, the inorder Successor of the left child node will be the root node.

What are the time complexity and space complexity of populating the inorder Successor for all nodes using the stack method?

The time complexity will be O(n), and the space complexity will be O(h), where n is the number of nodes and h is the height of the tree.

What is reverse inorder traversal?

The reverse inorder traversal is nothing but the complete opposite of inorder traversal.

Let us now conclude this article in the next section.

Conclusion

In this article, we have extensively discussed how to populate an inorder Successor for all nodes for a given binary tree. We implemented it in C++ using two different approaches. We also used some examples to make it easier to understand.