# Modify a binary tree to get preorder traversal using right pointers only

Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers.

Examples:

```Input :    10
/
8      2
/
3     5
Output :    10

8

3

5

2
Explanation : The preorder traversal
of given binary tree is 10 8 3 5 2.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1 (Recursive)
One needs to make the right pointer of root point to the left subtree.
If the node has just left child, then just moving the child to right will complete the processing for that node.
If there is a right child too, then it should be made right child of the right-most of the original left subtree.
The above function used in the code process a node and then returns the rightmost node of the transformed subtree.

## C++

 `// C code to modify binary tree for ` `// traversal using only right pointer ` `#include ` `#include ` `#include ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// A binary tree node has data, ` `// left child and right child ` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `// function that allocates a new node ` `// with the given data and NULL left ` `// and right pointers. ` `struct` `Node* newNode(``int` `data) ` `{ ` `    ``struct` `Node* node = ``new` `struct` `Node; ` `    ``node->data = data; ` `    ``node->left = NULL; ` `    ``node->right = NULL; ` `    ``return` `(node); ` `} ` ` `  `// Function to modify tree ` `struct` `Node* modifytree(``struct` `Node* root) ` `{ ` `    ``struct` `Node* right = root->right; ` `    ``struct` `Node* rightMost = root; ` ` `  `    ``// if the left tree exists ` `    ``if` `(root->left) { ` ` `  `        ``// get the right-most of the ` `        ``// original left subtree ` `        ``rightMost = modifytree(root->left); ` ` `  `        ``// set root right to left subtree ` `        ``root->right = root->left; ` `        ``root->left = NULL; ` `    ``} ` ` `  `    ``// if the right subtree does ` `    ``// not exists we are done! ` `    ``if` `(!right)  ` `        ``return` `rightMost; ` ` `  `    ``// set right pointer of right-most ` `    ``// of the original left subtree ` `    ``rightMost->right = right; ` ` `  `    ``// modify the rightsubtree ` `    ``rightMost = modifytree(right); ` `    ``return` `rightMost; ` `} ` ` `  `// printing using right pointer only ` `void` `printpre(``struct` `Node* root) ` `{ ` `    ``while` `(root != NULL) { ` `        ``cout << root->data << ``" "``; ` `        ``root = root->right; ` `    ``} ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``/* Constructed binary tree is ` `         ``10 ` `        ``/ ` `       ``8   2 ` `      ``/    ` `     ``3   5     */` `    ``struct` `Node* root = newNode(10); ` `    ``root->left = newNode(8); ` `    ``root->right = newNode(2); ` `    ``root->left->left = newNode(3); ` `    ``root->left->right = newNode(5); ` ` `  `    ``modifytree(root); ` `    ``printpre(root); ` ` `  `    ``return` `0; ` `} `

## Python3

 `# Python code to modify binary tree for  ` `# traversal using only right pointer  ` ` `  `class` `newNode():  ` ` `  `    ``def` `__init__(``self``, data):  ` `        ``self``.data ``=` `data ` `        ``self``.left ``=` `None` `        ``self``.right ``=` `None` `         `  `         `  `# Function to modify tree  ` `def` `modifytree(root): ` ` `  `    ``right ``=` `root.right  ` `    ``rightMost ``=` `root  ` ` `  `    ``# if the left tree exists  ` `    ``if` `(root.left): ` ` `  `        ``# get the right-most of the  ` `        ``# original left subtree  ` `        ``rightMost ``=` `modifytree(root.left)  ` ` `  `        ``# set root right to left subtree  ` `        ``root.right ``=` `root.left  ` `        ``root.left ``=` `None` `     `  ` `  `    ``# if the right subtree does  ` `    ``# not exists we are done!  ` `    ``if` `(``not` `right): ` `        ``return` `rightMost  ` ` `  `    ``# set right pointer of right-most  ` `    ``# of the original left subtree  ` `    ``rightMost.right ``=` `right  ` ` `  `    ``# modify the rightsubtree  ` `    ``rightMost ``=` `modifytree(right)  ` `    ``return` `rightMost  ` ` `  ` `  `# printing using right pointer only  ` `def` `printpre(root): ` ` `  `    ``while` `(root !``=` `None``): ` `        ``print``(root.data,end``=``" "``) ` `        ``root ``=` `root.right  ` `         `  `# Driver code ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``""" Constructed binary tree is ` `    ``10  ` `        ``/   ` `    ``8 2  ` `    ``/   ` `    ``3 5  """` `    ``root ``=` `newNode(``10``)  ` `    ``root.left ``=` `newNode(``8``)  ` `    ``root.right ``=` `newNode(``2``)  ` `    ``root.left.left ``=` `newNode(``3``)  ` `    ``root.left.right ``=` `newNode(``5``)  ` ` `  `    ``modifytree(root)  ` `    ``printpre(root) ` ` `  `# This code is contributed by SHUBHAMSINGH10 `

Output:

```10 8 3 5 2
```

Method 2 (Iterative)
This can be easily done using iterative preorder traversal. See here. Iterative preorder traversal
The idea is to maintain a variable prev which maintains the previous node of the preorder traversal. Every-time a new node is encountered, the node set its right to previous one and prev is made equal to the current node. In the end we will have a sort of linked list whose first element is root then left child then right, so on and so forth.

## C++

 `// C++ code to modify binary tree for ` `// traversal using only right pointer ` `#include ` `#include ` `#include ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// A binary tree node has data, ` `// left child and right child ` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `// Helper function that allocates a new ` `// node with the given data and NULL ` `// left and right  pointers. ` `struct` `Node* newNode(``int` `data) ` `{ ` `    ``struct` `Node* node = ``new` `struct` `Node; ` `    ``node->data = data; ` `    ``node->left = NULL; ` `    ``node->right = NULL; ` `    ``return` `(node); ` `} ` ` `  `// An iterative process to set the right ` `// pointer of Binary tree ` `void` `modifytree(``struct` `Node* root) ` `{ ` `    ``// Base Case ` `    ``if` `(root == NULL) ` `        ``return``; ` ` `  `    ``// Create an empty stack and push root to it ` `    ``stack nodeStack; ` `    ``nodeStack.push(root); ` ` `  `    ``/* Pop all items one by one.  ` `        ``Do following for every popped item ` `       ``a) print it ` `       ``b) push its right child ` `       ``c) push its left child ` `    ``Note that right child is pushed first ` `    ``so that left is processed first */` `    ``struct` `Node* pre = NULL; ` `    ``while` `(nodeStack.empty() == ``false``) { ` ` `  `        ``// Pop the top item from stack ` `        ``struct` `Node* node = nodeStack.top(); ` ` `  `        ``nodeStack.pop(); ` ` `  `        ``// Push right and left children of ` `        ``// the popped node to stack ` `        ``if` `(node->right) ` `            ``nodeStack.push(node->right); ` `        ``if` `(node->left) ` `            ``nodeStack.push(node->left); ` ` `  `        ``// check if some previous node exists ` `        ``if` `(pre != NULL) { ` ` `  `            ``// set the right pointer of ` `            ``// previous node to currrent ` `            ``pre->right = node; ` `        ``} ` ` `  `        ``// set previous node as current node ` `        ``pre = node; ` `    ``} ` `} ` ` `  `// printing using right pointer only ` `void` `printpre(``struct` `Node* root) ` `{ ` `    ``while` `(root != NULL) { ` `        ``cout << root->data << ``" "``; ` `        ``root = root->right; ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``/* Constructed binary tree is ` `            ``10 ` `          ``/   ` `        ``8      2 ` `      ``/       ` `    ``3     5   ` `  ``*/` `    ``struct` `Node* root = newNode(10); ` `    ``root->left = newNode(8); ` `    ``root->right = newNode(2); ` `    ``root->left->left = newNode(3); ` `    ``root->left->right = newNode(5); ` ` `  `    ``modifytree(root); ` `    ``printpre(root); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java code to modify binary tree for  ` `// traversal using only right pointer  ` `import` `java.util.*; ` `class` `GfG { ` ` `  `// A binary tree node has data,  ` `// left child and right child  ` `static` `class` `Node {  ` `    ``int` `data;  ` `    ``Node left;  ` `    ``Node right;  ` `} ` ` `  `// Helper function that allocates a new  ` `// node with the given data and NULL  ` `// left and right pointers.  ` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node node = ``new` `Node();  ` `    ``node.data = data;  ` `    ``node.left = ``null``;  ` `    ``node.right = ``null``;  ` `    ``return` `(node);  ` `}  ` ` `  `// An iterative process to set the right  ` `// pointer of Binary tree  ` `static` `void` `modifytree(Node root)  ` `{  ` `    ``// Base Case  ` `    ``if` `(root == ``null``)  ` `        ``return``;  ` ` `  `    ``// Create an empty stack and push root to it  ` `    ``Stack nodeStack = ``new` `Stack ();  ` `    ``nodeStack.push(root);  ` ` `  `    ``/* Pop all items one by one.  ` `        ``Do following for every popped item  ` `    ``a) print it  ` `    ``b) push its right child  ` `    ``c) push its left child  ` `    ``Note that right child is pushed first  ` `    ``so that left is processed first */` `    ``Node pre = ``null``;  ` `    ``while` `(nodeStack.isEmpty() == ``false``) {  ` ` `  `        ``// Pop the top item from stack  ` `        ``Node node = nodeStack.peek();  ` ` `  `        ``nodeStack.pop();  ` ` `  `        ``// Push right and left children of  ` `        ``// the popped node to stack  ` `        ``if` `(node.right != ``null``)  ` `            ``nodeStack.push(node.right);  ` `        ``if` `(node.left != ``null``)  ` `            ``nodeStack.push(node.left);  ` ` `  `        ``// check if some previous node exists  ` `        ``if` `(pre != ``null``) {  ` ` `  `            ``// set the right pointer of  ` `            ``// previous node to currrent  ` `            ``pre.right = node;  ` `        ``}  ` ` `  `        ``// set previous node as current node  ` `        ``pre = node;  ` `    ``}  ` `}  ` ` `  `// printing using right pointer only  ` `static` `void` `printpre(Node root)  ` `{  ` `    ``while` `(root != ``null``) {  ` `        ``System.out.print(root.data + ``" "``);  ` `        ``root = root.right;  ` `    ``}  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `main(String[] args)  ` `{  ` `    ``/* Constructed binary tree is  ` `            ``10  ` `        ``/   ` `        ``8     2  ` `    ``/       ` `    ``3     5  ` `*/` `    ``Node root = newNode(``10``);  ` `    ``root.left = newNode(``8``);  ` `    ``root.right = newNode(``2``);  ` `    ``root.left.left = newNode(``3``);  ` `    ``root.left.right = newNode(``5``);  ` ` `  `    ``modifytree(root);  ` `    ``printpre(root);  ` ` `  `} ` `}  `

## C#

 `// C# code to modify binary tree for  ` `// traversal using only right pointer  ` `using` `System;  ` `using` `System.Collections; ` ` `  `class` `GfG  ` `{ ` ` `  `// A binary tree node has data,  ` `// left child and right child  ` `public` `class` `Node  ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node left;  ` `    ``public` `Node right;  ` `} ` ` `  `// Helper function that allocates a new  ` `// node with the given data and NULL  ` `// left and right pointers.  ` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node node = ``new` `Node();  ` `    ``node.data = data;  ` `    ``node.left = ``null``;  ` `    ``node.right = ``null``;  ` `    ``return` `(node);  ` `}  ` ` `  `// An iterative process to set the right  ` `// pointer of Binary tree  ` `static` `void` `modifytree(Node root)  ` `{  ` `    ``// Base Case  ` `    ``if` `(root == ``null``)  ` `        ``return``;  ` ` `  `    ``// Create an empty stack and Push root to it  ` `    ``Stack nodeStack = ``new` `Stack();  ` `    ``nodeStack.Push(root);  ` ` `  `    ``/* Pop all items one by one.  ` `        ``Do following for every Popped item  ` `    ``a) print it  ` `    ``b) Push its right child  ` `    ``c) Push its left child  ` `    ``Note that right child is Pushed first  ` `    ``so that left is processed first */` `    ``Node pre = ``null``;  ` `    ``while` `(nodeStack.Count !=0)  ` `    ``{  ` ` `  `        ``// Pop the top item from stack  ` `        ``Node node = (Node)nodeStack.Peek();  ` ` `  `        ``nodeStack.Pop();  ` ` `  `        ``// Push right and left children of  ` `        ``// the Popped node to stack  ` `        ``if` `(node.right != ``null``)  ` `            ``nodeStack.Push(node.right);  ` `        ``if` `(node.left != ``null``)  ` `            ``nodeStack.Push(node.left);  ` ` `  `        ``// check if some previous node exists  ` `        ``if` `(pre != ``null``)  ` `        ``{  ` ` `  `            ``// set the right pointer of  ` `            ``// previous node to currrent  ` `            ``pre.right = node;  ` `        ``}  ` ` `  `        ``// set previous node as current node  ` `        ``pre = node;  ` `    ``}  ` `}  ` ` `  `// printing using right pointer only  ` `static` `void` `printpre(Node root)  ` `{  ` `    ``while` `(root != ``null``)  ` `    ``{  ` `        ``Console.Write(root.data + ``" "``);  ` `        ``root = root.right;  ` `    ``}  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `Main(String []args)  ` `{  ` `    ``/* Constructed binary tree is  ` `            ``10  ` `        ``/   ` `        ``8     2  ` `    ``/       ` `    ``3     5  ` `*/` `    ``Node root = newNode(10);  ` `    ``root.left = newNode(8);  ` `    ``root.right = newNode(2);  ` `    ``root.left.left = newNode(3);  ` `    ``root.left.right = newNode(5);  ` ` `  `    ``modifytree(root);  ` `    ``printpre(root);  ` `} ` `}  ` ` `  `// This code is contributed by ` `// Arnab Kundu `

Output:

```10 8 3 5 2
```

## tags:

Stack Tree Stack Tree