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.
Sample Example
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is Tree Traversal?
3.2.
What is the Time Complexity of Inorder Traversal?
3.3.
What is the difference between Inorder, Preorder and Postorder Traversal?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Convert left-right representation of a binary tree to down-right

Author Akshit Mehra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss the problem of giving a Binary Tree with a left-right representation to a Top-Down Representation.

Tree Data Structure: A tree is a non-linear data structure that stores data in a hierarchical way instead of storing it linearly.  

Left-Right representation: A binary tree's Left-Right representation is a standard representation in which each node includes a reference to the left child and another pointer to the right child.

Down-Right representation: Every node in the Down-Right format has a reference to the left (or first) child and another pointer to the next sibling. As a result, siblings on all levels are linked from left to right.

Problem Statement

The problem above states that converting a given binary tree with left right representation to its down-right representation.

Sample Example

Example: Given the below binary tree

                                          

Output:

                                     

Explanation: Each left Pointer of a node acts as a down pointer, and therefore the link remains the same. While each of the right pointers points to the next sibling node, which can be seen above.

Also See, Binary Tree Postorder Traversal.

Approach

To solve the above problem, we use the recursive approach of Binary tree traversal. Below is the solution:

  1. Pass the root and its right child to the function.
  2. Store the old value of the right sibling in a temp node.
  3. Point the left pointer of the node to the sibling.
  4. Call the function recursively for the left node, and pass the old stored right child as the sibling.
  5. Call the function recursively for the right node, and pass NULL as the sibling node.

Pseudocode

DownRight(root, sibling):
	If root is none:
		Return
	old_val = root->right;
	root->right = sibling;	
	DownRight(root->left, old_val);
	DownRight(root->right, NULL)

Implementation in C++

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

// Class for defining a Tree Node;
class Node{
    public:
    int value;
    Node* left;
    Node* right;
};

// Function to construct a new Node;
Node* NewNode(int val){
    Node* node = new Node;
    node->value = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}

//To check if a leaf node;
bool leaf(Node* root){
    return(!root->left && !root->right);
}

//Function For TopDown Tree Construction
void TopDown(Node* root,  Node* sib){
    //If Null root value
    if(!root){
        return;
    }

    //Storing the old value of right sibling
    Node* b = root->right;
    //Changing the right pointer to sibling
    root->right = sib;

    //Function for left node
    TopDown(root->left, b);

    //Calling for right node;
    TopDown(root->right, NULL);

}
//Function of Right Down traversal;
void RightDown(Node* root){
    if(!root){
        return;
    }
    cout<<root->value<<" ";
    RightDown(root->right);
    RightDown(root->left);
}
void solve()
{  
    Node* root = NewNode(1);
    root->left = NewNode(2);
    root->right = NewNode(3);
    root->left->left = NewNode(4);
    root->left->right = NewNode(5);
    root->right->left = NewNode(6);
    root->right->right = NewNode(7);
    // root->right->right->right = NewNode(8);
   
    RightDown(root);
    cout<<"\n";
    TopDown(root, NULL);
    RightDown(root);
}  
int main()
{
    solve();
    return 0;
}

 

Output:

1 3 7 6 2 5 4 
1 2 3 6 7 4 5

Complexity Analysis

Time complexity: O(n)

Explanation: As in the above approach, we traverse each node of the Tree only once. Therefore, the Time Complexity of the Tree is O(n).  

Space complexity: O(log(n))

Explanation: In the above approach, the space complexity is due to the recursive function. The maximum depth of the recursive call for the above function is equivalent to the Tree's height. For a binary tree, it is log(n), where n is the number of nodes in a tree. 

Therefore, the worst-case Space complexity is O(log(n)). 

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 Tree Traversal?

Tree traversal refers to the traversal of each node of a tree Data-structure. Tree traversal can be off 3 types:

  1. Inorder Traversal
  2. Preorder Traversal
  3. Postorder Traversal

 

The time complexity of each of the above traversals is O(n).

What is the Time Complexity of Inorder Traversal?

As we can see in the above algorithm, we see that we visit every node of the Tree only once. Therefore, the time complexity of the Inorder Traversal is O(n), where n is the number of nodes in the Tree.

What is the difference between Inorder, Preorder and Postorder Traversal?

  1. In order, you travel from the left subtree to the root, then to the right subtree.
  2. You go from the root to the left subtree, then to the right subtree for Preorder.
  3. You go from the left subtree to the right subtree, then to the root, in Post order.

Conclusion

This article discusses the problem of converting a given binary tree with a left-right representation to its down-right representation. Once complete, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

 

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning 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 problemsinterview 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!!

Live masterclass