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

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