Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Inorder traversal
3.
Problem statement
4.
Solution
4.1.
1st Approach(Using reverse inorder traversal)
4.1.1.
Algorithm
4.1.2.
Code
4.1.3.
Output
4.2.
2nd Approach(Using stack)
4.2.1.
Algorithm
4.2.2.
Code
4.2.3.
Output
5.
Frequently asked questions
5.1.
What is Inorder traversal?
5.2.
How many types of traversal are there?
5.3.
What do you mean by Inorder Successor?
5.4.
What are the time complexity and space complexity of populating the inorder Successor for all nodes using the stack method?
5.5.
What is reverse inorder traversal?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Populate Inorder Successor for all node

Author Ankit Kumar
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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.

struct node {
   int value;
   struct node* left;
   struct node* right;
   struct node* next;
}

 

 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.

Also check out - Inorder Predecessor

Frequently asked questions

What is Inorder traversal?

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.

After reading about how to populate Inorder Successor for all nodes, are you not feeling excited to read/explore more articles on related topics? Don't worry. Coding ninjas has you covered. To learn more, see  Level order traversal with direction change after every two levelsConstructing a binary tree from two traversal SequencesPerfect Binary Tree Specific Level Order Traversal or you can also try out some Gate Questions on Tree Traversal.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Iterative Preorder Traversal of Binary tree
Next article
Create a tree with Left-Child Right Sibling
Live masterclass