Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Explanation of the problem 
1.3.
Sample Example 
2.
Approach to the problem 
2.1.
Steps of the approach
2.2.
Implementation in C++ 
2.3.
Complexity Analysis 
2.4.
Iterative Implementation in C++
2.5.
Complexity Analysis 
3.
Frequently Asked Questions
3.1.
What is a binary tree?
3.2.
What is a skewed binary tree?  
3.3.
What is a pointer? 
4.
Conclusion
Last Updated: Mar 27, 2024

Modify a Binary Tree to get Preorder Traversal using Right Pointers only

Author Vidhi Singh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Binary trees are one of the most prominent data structures discussed in technical interviews. It holds such importance as it tends to test the candidate’s knowledge of not only the data structures but also get an idea of this logical and thinking ability. 

So, in this article, we will discuss the problem: Modify a binary tree to get preorder traversal using right pointers only in detail. 

Also See, Binary Tree Postorder Traversal.

Problem Statement 

Given a binary tree, write a function that modifies it in such a way that its preorder traversal can be obtained using only the right pointer.  

Explanation of the problem 

You will be given a binary tree. You have to rearrange its nodes such that using its right pointers, only preorder traversal of the original tree can be obtained.  

If a binary tree is as follows: 

Then, the preorder traversal will be A B D E C. 
To get a preorder traversal of a binary tree, the rule used is -visit the node, then the left child, and finally the right child.

The question does not, in any sense, says that while modification left pointer and right pointer both can be used. It is just that, after modification, only the right pointers have to be used. 

Sample Example 

For the given binary tree: 

The binary tree after modification will be as follows:

Approach to the problem 

According to the question, you are supposed to think of how you can rearrange the nodes of the binary tree so that after rearrangement, only the right pointers are used when preorder traversal is performed. After modification, the usage of the left pointer should not be required. And preorder traversal has been explained earlier in this article.

So, if you observe carefully, it is like making the left child of a node its right child, and then the right child of the considered node is made the right child of the rightmost child of the left child of the considered node. 

If a node does not have a right child, the left child can be made the right child.

Another observation is that it always results in a right-skewed tree.

It might have been a little confusing at this point. To make it clear, let us take an example.  

If we have the following binary tree:

Going as per what we have described above, 

Step 1: 

Step 2:

It was a small binary tree, so it took only two steps. Although the check would be done on further nodes, but no more modifications will happen.   

Steps of the approach

  1. For a given node in a binary tree:
    1.1. If the node has no right child, then move the left the child to the right
    1.2. If a right child is present, then make it the right child of the right-most of the original left subtree.  
  2. Repeat step 1 till you reach the node with no child at all. 

Implementation in C++ 

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

class node		//Class of node
{
	public:
    	char val;
    	node* left,* right;
};

node* new_node(char value)		//Creating a new node
{
	node* t=new node;
	t->val=value;
	t->left->right==NULL;
	return t;
}


node* modification(node* parent)	 //Modifying the binary tree
{
	node* right=parent->right;
	node* right_most=parent;


	if(parent->left)
	{
		right_most=modification(parent->left);
		parent->right =parent->left;
		parent->left=NULL;
	}
	if(!right)
		return right_most;

	right_most->right=right;
	right_most=modification(right);
	return right_most;
}

void preorder_traversal(node* root)		//Preorder only using right pointer
{
	while(root!=NULL) 
	{
		cout<<root->val<<" ";
		root=root->right;
	}
}

int main()
{
	return 0;
}

 

Input: 

node* root=new_node('A');
root->left=new_node('B');
root->right=new_node('C');
root->left->left=new_node('D');
root->left->right=new_node('E');
modification(root); 
cout<<"Preorder traversal is: ";
preorder_traversal(root);


Output:

Preorder traversal is: A B D E C  

Complexity Analysis 

Time Complexity: O(n) 
Here, n is the total nodes in the binary tree. 

Space Complexity: O(n)
The recursion stack takes up the auxiliary space. 

Note: The above approach is recursive. The same thing can be implemented in an iterative manner. 

For that, we need to maintain a variable, let us say ‘p’,  to store the previous node of the preorder traversal. Every time the node makes its right to the previous one, the p is equal to the current node. Finally, we will have a linked list whose first element is the root, then the left child, then the right, and the same continues. You can read more about Iterative Preorder Traversal here.

Iterative Implementation in C++

#include<bits/stdc++.h>
using namespace std;
 
class node		//Class of new node
{
    public:
        char val;
        node* left,*right;
};

node* new_node(char value)		//Creating a new node
{
    node* t=new node;
    t->val=value;
    t->left=NULL;
    t->right=NULL;
    return t;
}
 
void modification(node* parent)		//Modifying the binary tree
{
    if(parent==NULL)
        return;
 
    stack<node*> nodes;
    nodes.push(parent);
    node* p=NULL;
    while(nodes.empty()==false) 
    {
        node* t=nodes.top();
        nodes.pop();
        if(t->right)
            nodes.push(t->right);
        if (t->left)
            nodes.push(t->left);
 
         if(p!=NULL) 
         {
            p->right=t;
        }
        p=t;
    }
}

void preorder_traversal(node* root)		//Preorder traversal using right pointer
{
    while(root!=NULL)
    {
        cout<<root->val<<" ";
        root=root->right;
    }
}

int main()
{ 
    return 0;
}

 

Input:

node* root=new_node('A');
root->left=new_node('B');
root->right=new_node('C');
root->left->left=new_node('D');
root->left->right=new_node('E');
 
cout<<"The preorder traversal is: "
modification(root);
preorder_traversal(root);

 

Output:

The preorder traversal is: A B D E C  

Complexity Analysis 

Time Complexity: O(n) 
Here, n is the total nodes in the binary tree. 

Space Complexity: O(n)
The stack takes up the auxiliary space. 

Check out this problem - Mirror A Binary Tree

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

Frequently Asked Questions

What is a binary tree?

A binary tree is one of the data structures that represents a hierarchical relation of nodes.

What is a skewed binary tree?  

A skewed binary tree is one of the types of binary trees where all nodes except one node have only one child. That one node has no child.  

What is a pointer? 

A pointer can be considered as a memory location where data is stored. Basically, pointers help in accessing that memory location.

Conclusion

This article extensively discusses the programming problem: Modify a Binary Tree to get Preorder Traversal using Right Pointers only, along with their pseudocode, implementation, and time trade-offs.

We hope that this blog has helped you enhance your knowledge regarding Modify a Binary
Tree to get Preorder Traversal using Right Pointers only, and if you would like to learn more, check out our articles on Coding Ninjas Blogs

 

Recommended problems -


You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem 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 organized 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 Courses to give your career an edge over others!

Do upvote our blog to help other ninjas grow. 

Happy Coding! 

Previous article
Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree
Next article
Traversal in Binary Tree
Live masterclass