Modify the binary tree to get the pre-order traversal using only the right pointer

Given a binary tree. Make a modification so that after the modification, it can be traversed in order using only the correct pointers. During modification, you can use both the right and left pointers.

Example:

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: Try the following {IDE} first, before proceeding with the solution.

Method 1 (Recursive)

You need to make the right pointer of the root point to the left subtree.

If the node happens to have a left child node, you can simply move the child node to the right to complete the processing of the node.

If there are also suitable children, then they should

The rightmost right child of the original left subtree.

The above function used in the code processes 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 <bits/stdc++.h>
  
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;
}

Java

//Java code to modify binary tree for 
//traversal using only right pointer 
class GFG
{
  
//A binary tree node has data, //left child and right child 
static class Node 
{ 
     int data; 
     Node left; 
     Node right; 
}; 
  
//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); 
} 
  
//Function to modify tree 
static Node modifytree( Node root) 
{ 
     Node right = root.right; 
     Node rightMost = root; 
  
     //if the left tree exists 
     if (root.left != null ) 
     { 
  
         //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 == null ) 
         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 
static void printpre( Node root) 
{ 
     while (root != null ) 
     { 
         System.out.print( root.data + " " ); 
         root = root.right; 
     } 
} 
  
//Driver cde 
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

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

C#

//C# code to modify binary tree for 
//traversal using only right pointer
using System;
      
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; 
}; 
  
//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); 
} 
  
//Function to modify tree 
static Node modifytree( Node root) 
{ 
     Node right = root.right; 
     Node rightMost = root; 
  
     //if the left tree exists 
     if (root.left != null ) 
     { 
  
         //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 == null ) 
         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 
static void printpre( Node root) 
{ 
     while (root != null ) 
     { 
         Console.Write( root.data + " " ); 
         root = root.right; 
     } 
} 
  
//Driver cde 
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 29AjayKumar

The output is as follows:

10 8 3 5 2

Method 2 (Iterative)

This can be easily done using iteration’s pre-order traversal. Look here.

Iterative traversal

The idea is to maintain a variable prev, which maintains the previous node of the pre-order traversal. Each time a new node is encountered, the node sets its permissions to the previous node, and the previous node equals the current node. Finally, we will get a kind of linked list whose first element is root, then left child, then right, and so on.

C ++

//C++ code to modify binary tree for
//traversal using only right pointer
#include <iostream>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
  
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<Node*> 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<Node> nodeStack = new Stack<Node> (); 
     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); 
  
}
}

python

# Python code to modify binary tree for 
# traversal using only right pointer 
  
# A binary tree node has data, # left child and right child 
class newNode(): 
  
     def __init__( self , data): 
         self .data = data 
         self .left = None
         self .right = None
  
# An iterative process to set the right 
# pointer of Binary tree 
def modifytree( root):
      
     # Base Case 
     if (root = = None ):
         return
          
     # Create an empty stack and append root to it 
     nodeStack = []
     nodeStack.append(root) 
      
     ''' Pop all items one by one. 
     Do following for every popped item 
     a) prit 
     b) append its right child 
     c) append its left child 
     Note that right child is appended first 
     so that left is processed first '''
     pre = None
     while ( len (nodeStack)):
          
         # Pop the top item from stack 
         node = nodeStack[ - 1 ]
         nodeStack.pop() 
          
         # append right and left children of 
         # the popped node to stack 
         if (node.right):
             nodeStack.append(node.right)
         if (node.left):
             nodeStack.append(node.left) 
              
         # check if some previous node exists 
         if (pre ! = None ):
              
             # 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 
def printpre( root):
     while (root ! = None ):
         print (root.data, end = " " )
         root = root.right 
      
# Driver code 
  
''' 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

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

The output is as follows:

10 8 3 5 2