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

Last Updated : 02 Aug, 2022

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.

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.

Implementation:

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 

Javascript

<script>
 
    // JavaScript code to modify binary tree for
    // traversal using only right pointer
     
    // A binary tree node has data,
    // left child and right child
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
 
    // function that allocates a new node
    // with the given data and null left
    // and right pointers.
    function newNode(data)
    {
        let node = new Node(data);
        return (node);
    }
 
    // Function to modify tree
    function modifytree(root)
    {
        let right = root.right;
        let 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
    function printpre(root)
    {
        while (root != null)
        {
            document.write( root.data + " ");
            root = root.right;
        }
    }
     
    /* Constructed binary tree is
        10
        / \
        8 2
        / \
        3 5 */
    let 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);
     
</script>

Output:

10 8 3 5 2

Time Complexity : O(n)
Auxiliary Space : O(n)

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.

Implementation:

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 current
            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 current 
            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) print 
    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 current 
            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 current 
            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

Javascript

<script>
 
    // JavaScript code to modify binary tree for
    // traversal using only right pointer
     
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
 
    // Helper function that allocates a new
    // node with the given data and NULL
    // left and right pointers.
    function newNode(data)
    {
        let node = new Node(data);
        return (node);
    }
 
    // An iterative process to set the right
    // pointer of Binary tree
    function modifytree(root)
    {
        // Base Case
        if (root == null)
            return;
 
        // Create an empty stack and push root to it
        let 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 */
        let pre = null;
        while (nodeStack.length > 0) {
 
            // Pop the top item from stack
            let node = nodeStack[nodeStack.length - 1];
 
            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 current
                pre.right = node;
            }
 
            // set previous node as current node
            pre = node;
        }
    }
 
    // printing using right pointer only
    function printpre(root)
    {
        while (root != null) {
            document.write(root.data + " ");
            root = root.right;
        }
    }
     
    /* Constructed binary tree is
            10
            / \
            8  2
           / \    
          3   5
    */
    let 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);
 
</script>

Output:

10 8 3 5 2

Time Complexity : O(n)
Auxiliary Space : O(n)

aditya314

Improve

Previous Article

Find distance between two nodes of a Binary Tree

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Similar Reads

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver

Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each

Modify Binary Tree by replacing each node with the sum of its Preorder Predecessor and Successor

Given a binary tree consisting of N nodes, the task is to replace each node in the binary tree with the sum of its preorder predecessor and preorder successor. Examples: Input: 2 / \ 3 4 / \ / \ 6 5 7 8 Output: 3 / \ 8 12 / \ / \ 8 10 12 7 Explanation: For Node 2: Preorder predecessor = 0 (as preorder predecessor is not present), preorder successor

Preorder, Postorder and Inorder Traversal of a Binary Tree using a single Stack

Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-order, and In-order iteratively using only one stack traversal. Examples: Input: Output:Preorder Traversal: 1 2 3Inorder Traversal: 2 1 3Postorder Traversal: 2 3 1 Input: Output:Preorder traversal: 1 2 4 5 3 6 7Inorder traversal: 4 2 5 1 6 3 7Post-order tr

Find postorder traversal of BST from preorder traversal

Given an array representing preorder traversal of BST, print its postorder traversal. Examples: Input : 40 30 35 80 100 Output : 35 30 100 80 40 Input : 40 30 32 35 80 90 100 120 Output : 35 32 30 120 100 90 80 40 Prerequisite: Construct BST from given preorder traversal Simple Approach: A simple solution is to first construct BST from a given preo

Find n-th node in Preorder traversal of a Binary Tree

Given a Binary tree and a number N, write a program to find the N-th node in the Preorder traversal of the given Binary tree. Prerequisite: Tree Traversal Examples: Input: N = 4 11 / \ 21 31 / \ 41 51 Output: 51 Explanation: Preorder Traversal of given Binary Tree is 11 21 41 51 31, so 4th node will be 51. Input: N = 5 25 / \ 20 30 / \ / \ 18 22 24

Construct a Perfect Binary Tree from Preorder Traversal

Given an array pre[], representing the Preorder traversal of a Perfect Binary Tree consisting of N nodes, the task is to construct a Perfect Binary Tree from the given Preorder Traversal and return the root of the tree. Examples: Input: pre[] = {1, 2, 4, 5, 3, 6, 7}Output: 1 / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 7 Input: pre[] = {1, 2, 3}Output: 1 / \

Check if a given array can represent Preorder Traversal of Binary Search Tree

Given an array of numbers, return true if given array can represent preorder traversal of a Binary Search Tree, else return false. Expected time complexity is O(n). Examples: Input: pre[] = {2, 4, 3} Output: true Given array can represent preorder traversal of below tree 2 \ 4 / 3 Input: pre[] = {2, 4, 1} Output: false Given array cannot represent

Preorder Traversal of Binary Tree

Preorder traversal is defined as a type of tree traversal that follows the Root-Left-Right policy where: The root node of the subtree is visited first.Then the left subtree is traversed.At last, the right subtree is traversed. Algorithm for Preorder Traversal of Binary TreeThe algorithm for preorder traversal is shown as follows: Preorder(root): F

Convert Binary Tree to Doubly Linked List by fixing left and right pointers

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the

Article Tags :

Practice Tags :