## 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:

- Pass the root and its right child to the function.
- Store the old value of the right sibling in a temp node.
- Point the left pointer of the node to the sibling.
- Call the function recursively for the left node, and pass the old stored right child as the sibling.
- 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__