Skip to main content

Reverse the path from given node to root node

"Reverse the path from given node to root node" means to reverse the order of nodes along the path that goes from the given node to the root node in a tree or a graph.

In a tree or graph, each node has a parent, except the root node which has no parent. The path from a given node to the root node consists of all the nodes on the way from the given node to the root node, including the given node and the root node itself.

Reverse the path values form given node

To reverse the path from the given node to the root node, we start with the given node and follow the parent links until we reach the root node. Then we reverse the order of the nodes along this path, so that the root node becomes the first node, and the given node becomes the last node.

Program Solution

/*
C++ Program 
Reverse the path from given node to root node
*/
#include<iostream>

using namespace std;
class Node {
  public:
    int data;
  Node *left, *right;
  Node(int value) {
    this->data = value;
    this->left = this->right = NULL;
  }
};
class Stack {
  public:
    Node *element;
  Stack *next;
  int status;
  Stack(Node *node) {
    this->element = node;
    this->next = NULL;
    this->status = 0;
  }
};
class BinaryTree {
  public:
    Node *root;
  Stack *top;
  BinaryTree() {
    this->root = NULL;
    this->top = NULL;
  }
  void preorder(Node *node) {
    if (node != NULL) {
      cout << "  " << node->data;
      this->preorder(node->left);
      this->preorder(node->right);
    }
  }
  void changePath(Node *node, int value) {
    if (node != NULL) {
      Node *temp = node;
      int status = 0;
      push(node);
      while (this->top != NULL || temp != NULL) {
        (this->top->status) ++;
        if (this->top->status == 1) {
          temp = temp->left;
        } else
        if (this->top->status == 2) {
          temp = temp->right;
        } else {
          if (this->top->element->data == value) {
            status = 1;
            break;
          }
          temp = NULL;
          pop();
        }
        if (temp != NULL) {
          push(temp);
        }
        if (this->top != NULL) {
          temp = this->top->element;
        } else {
          temp = NULL;
        }
      }
      if (status == 1) {
        Stack *back = NULL, *hold = NULL;
        while (this->top != NULL) {
          back = this->top;
          while (back->next != NULL) {
            hold = back;
            back = back->next;
          }
          value = back->element->data;
          back->element->data = this->top->element->data;
          this->top->element->data = value;
          back->element = NULL;
          if (hold != NULL) {
            hold->next = NULL;
          }
          pop();
        }
      } else {
        cout << "Node " << value << " are not Exist";
      }
    } else {
      cout << "Empty Binary Tree" << endl;
    }
  }
  void push(Node *node) {
    Stack *new_node = new Stack(node);
    new_node->next = this->top;
    this->top = new_node;
  }
  void pop() {
    if (this->top != NULL) {
      Stack *remove = this->top;
      this->top = this->top->next;
      remove->next = NULL;
      remove->element = NULL;
      delete remove;
      remove = NULL;
    }
  }
};
int main() {
  BinaryTree *obj = new BinaryTree();

  /* Create Binary Tree
  -----------------------
         10
       /    \
      2      5
     / \    /  \
    1   3  7    2
       /    \
      9      -4
  */

  obj->root = new Node(10);
  obj->root->left = new Node(2);
  obj->root->right = new Node(5);
  obj->root->right->right = new Node(2);
  obj->root->right->left = new Node(7);
  obj->root->left->left = new Node(1);
  obj->root->left->right = new Node(3);
  obj->root->left->right->left = new Node(9);
  obj->root->right->left->right = new Node(-4);
  obj->preorder(obj->root);
  cout << endl;
  obj->changePath(obj->root, 9);
  obj->preorder(obj->root);
  return 0;
}

Output

  10  2  1  3  9  5  7  -4  2
  9  3  1  2  10  5  7  -4  2
/*
Java Program 
Reverse the path from given node to root node
*/

//Structure of Binary Tree node
class Node {

  public int data;
  public Node left, right;
  //make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = right = null;
  }
}

class Stack {

  public Node element;
  public Stack next;
  public int status;
  public Stack(Node node) {
    element = node;
    next = null;
    status = 0;
  }
}

public class BinaryTree {

  public Node root;
  private Stack top;
  public BinaryTree() {
    //set initial tree root to null
    root = null;
    //set stack is null
    top = null;
  }


  //Display tree element preorder form
  public void preorder(Node node) {

    if (node != null) {
      //Print node value
      System.out.print("  " + node.data);
      preorder(node.left);
      preorder(node.right);
    }

  }
  //Change the path in reverse order by given node
  public void changePath(Node node, int value) {

    if (node != null) {

      Node temp = node;

      int status = 0;
      push(node); //add first node

      //Traversal of tree in postorder view
      while (top != null || temp != null) {

        (top.status) ++;

        if (top.status == 1) {
          temp = temp.left;
        } else if (top.status == 2) {
          temp = temp.right;
        } else {
          if (top.element.data == value) {
            status = 1;
            break;
          }
          temp = null;
          pop();

        }
        if (temp != null) {
          push(temp);
        }

        if (top != null) {
          temp = top.element;
        } else {
          temp = null;
        }
      }

      //Reverse tree path node value
      if (status == 1) {
        Stack back = null, hold = null;
        //change node data 
        while (top != null) {
          back = top;
          while (back.next != null) {
            hold = back;
            back = back.next;
          }

          value = back.element.data;
          back.element.data = top.element.data;
          top.element.data = value;
          //free last element
          back.element = null;
          if (hold != null) {
            hold.next = null;
          }
          pop();
        }
      } else {
        System.out.println("Node " + value + " are not Exist");
      }

    } else {
      System.out.println("Empty Binary Tree");
    }

  }

  //remove top element of stack
  public void push(Node node) {
    Stack new_node = new Stack(node);
    new_node.next = top;
    top = new_node;
  }
  //remove top element of the stack
  public void pop() {
    if (top != null) {
      Stack remove = top;
      top = top.next;
      remove.next = null;
      remove.element = null;

      remove = null;
    }
  }

  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();

    /* Make A Binary Tree
    -----------------------
           10
         /    \
        2      5
       / \    /  \
      1   3  7    2
         /    \
        9      -4
    */
    //insertion of binary Tree nodes
    obj.root = new Node(10);
    obj.root.left = new Node(2);
    obj.root.right = new Node(5);
    obj.root.right.right = new Node(2);
    obj.root.right.left = new Node(7);
    obj.root.left.left = new Node(1);
    obj.root.left.right = new Node(3);
    obj.root.left.right.left = new Node(9);
    obj.root.right.left.right = new Node(-4);
    obj.preorder(obj.root);
    System.out.println();
    obj.changePath(obj.root, 9);
    obj.preorder(obj.root);
  }
}

Output

  10  2  1  3  9  5  7  -4  2
  9  3  1  2  10  5  7  -4  2

#Python3 Program 
#Reverse the path from given node to root node

class Node :

  def __init__(self, value) :
    self.data = value
    self.left = self.right = None
  

class Stack :

  def __init__(self, node) :
    self.element = node
    self.next = None
    self.status = 0
  

class BinaryTree :

  def __init__(self) :
    self.root = None
    self.top = None
  
  def preorder(self, node) :
    if (node != None) :
      print( node.data,end=" ")
      self.preorder(node.left)
      self.preorder(node.right)
    
  
  def changePath(self, node, value) :
    if (node != None) :
      temp = node
      self.status = 0
      self.push(node)
      while (self.top != None or temp != None) :
        (self.top.status) += 1
        if (self.top.status == 1) :
          temp = temp.left
        elif (self.top.status == 2) :
          temp = temp.right
        else :
          if (self.top.element.data == value) :
            self.status = 1
            break
          
          temp = None
          self.pop()
        
        if (temp != None) :
          self.push(temp)
        
        if (self.top != None) :
          temp = self.top.element
        else :
          temp = None
        
      
      if (self.status == 1) :
        back = None
        hold = None
        while (self.top != None) :
          back = self.top
          while (back.next != None) :
            hold = back
            back = back.next
          
          value = back.element.data
          back.element.data = self.top.element.data
          self.top.element.data = value
          back.element = None
          if (hold != None) :
            hold.next = None
          
          self.pop()
        
      else :
        print("Node ", value ," are not Exist")
      
    else :
      print("Empty Binary Tree")
    
  
  def push(self, node) :
    new_node = Stack(node)
    new_node.next = self.top
    self.top = new_node
  
  def pop(self) :
    if (self.top != None) :
      remove = self.top
      self.top = self.top.next
      remove.next = None
      remove.element = None
      remove = None
    
  
def main() :
  obj = BinaryTree()



  #  Make Binary Tree
  #   
  #             10
  #           /    \
  #          2      5
  #         / \    /  \
  #        1   3  7    2
  #           /    \
  #          9      -4
  #      
  obj.root = Node(10)
  obj.root.left = Node(2)
  obj.root.right = Node(5)
  obj.root.right.right = Node(2)
  obj.root.right.left = Node(7)
  obj.root.left.left = Node(1)
  obj.root.left.right = Node(3)
  obj.root.left.right.left = Node(9)
  obj.root.right.left.right = Node(-4)
  obj.preorder(obj.root)
  print()
  obj.changePath(obj.root, 9)
  obj.preorder(obj.root)
  

if __name__ == "__main__":
  main()

Output

10 2 1 3 9 5 7 -4 2 
9 3 1 2 10 5 7 -4 2
/*
C# Program 
Reverse the path from given node to root node
*/
using System;
//Structure of Binary Tree node
class Node {

  public int data;
  public Node left, right;
  //make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = right = null;
  }
}

class Stack {

  public Node element;
  public Stack next;
  public int status;
  public Stack(Node node) {
    element = node;
    next = null;
    status = 0;
  }
}

class BinaryTree {

  public Node root;
  private Stack top;
  public BinaryTree() {
    //set initial tree root to null
    root = null;
    //set stack is null
    top = null;
  }


  //Display tree element preorder form
  public void preorder(Node node) {

    if (node != null) {
      //Print node value
      Console.Write("  " + node.data);
      preorder(node.left);
      preorder(node.right);
    }

  }
  //Change the path in reverse order by given node
  public void changePath(Node node, int value) {

    if (node != null) {

      Node temp = node;

      int status = 0;
      push(node); //add first node

      //Traversal of tree in postorder view
      while (top != null || temp != null) {

        (top.status) ++;

        if (top.status == 1) {
          temp = temp.left;
        } else if (top.status == 2) {
          temp = temp.right;
        } else {
          if (top.element.data == value) {
            status = 1;
            break;
          }
          temp = null;
          pop();

        }
        if (temp != null) {
          push(temp);
        }

        if (top != null) {
          temp = top.element;
        } else {
          temp = null;
        }
      }

      //Reverse tree path node value
      if (status == 1) {
        Stack back = null, hold = null;
        //change node data 
        while (top != null) {
          back = top;
          while (back.next != null) {
            hold = back;
            back = back.next;
          }

          value = back.element.data;
          back.element.data = top.element.data;
          top.element.data = value;
          //free last element
          back.element = null;
          if (hold != null) {
            hold.next = null;
          }
          pop();
        }
      } else {
        Console.WriteLine("Node " + value + " are not Exist");
      }

    } else {
      Console.WriteLine("Empty Binary Tree");
    }

  }

  //remove top element of stack
  public void push(Node node) {
    Stack new_node = new Stack(node);
    new_node.next = top;
    top = new_node;
  }
  //remove top element of the stack
  public void pop() {
    if (top != null) {
      Stack remove = top;
      top = top.next;
      remove.next = null;
      remove.element = null;

      remove = null;
    }
  }

  public static void Main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();

    /* Make A Binary Tree
      -----------------------
             10
           /    \
          2      5
         / \    /  \
        1   3  7    2
           /    \
          9      -4
      */
    //insertion of binary Tree nodes
    obj.root = new Node(10);
    obj.root.left = new Node(2);
    obj.root.right = new Node(5);
    obj.root.right.right = new Node(2);
    obj.root.right.left = new Node(7);
    obj.root.left.left = new Node(1);
    obj.root.left.right = new Node(3);
    obj.root.left.right.left = new Node(9);
    obj.root.right.left.right = new Node(-4);
    obj.preorder(obj.root);
    Console.WriteLine();
    obj.changePath(obj.root, 9);
    obj.preorder(obj.root);
  }
}

Output

  10  2  1  3  9  5  7  -4  2
  9  3  1  2  10  5  7  -4  2

<?php

/*
Php Program 
Reverse the path from given node to root node
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = $this->right = null;
  }
}
class Stack {
  public $element;
  public $next;
  public $status;

  function __construct($node) {
    $this->element = $node;
    $this->next = null;
    $this->status = 0;
  }
}
class BinaryTree {
  public $root;
  private $top;

  function __construct() {
    $this->root = null;
    $this->top = null;
  }
  public
  function preorder($node) {
    if ($node != null) {
      echo("  ". $node->data);
      $this->preorder($node->left);
      $this->preorder($node->right);
    }
  }
  public
  function changePath($node, $value) {
    if ($node != null) {
      $temp = $node;
      $this->status = 0;
      $this->push($node);
      while ($this->top != null || $temp != null) {
        $this->top->status++;
        if ($this->top->status == 1) {
          $temp = $temp->left;
        } else
        if ($this->top->status == 2) {
          $temp = $temp->right;
        } else {
          if ($this->top->element->data == $value) {
            $this->status = 1;
            break;;
          }
          $temp = null;
          $this->pop();
        }
        if ($temp != null) {
          $this->push($temp);
        }
        if ($this->top != null) {
          $temp = $this->top->element;
        } else {
          $temp = null;
        }
      }
      if ($this->status == 1) {
        $back = null;
        $hold = null;
        while ($this->top != null) {
          $back = $this->top;
          while ($back->next != null) {
            $hold = $back;
            $back = $back->next;
          }
          $value = $back->element->data;
          $back->element->data = $this->top->element->data;
          $this->top->element->data = $value;
          $back->element = null;
          if ($hold != null) {
            $hold->next = null;
          }
          $this->pop();
        }
      } else {
        echo("Node ". $value ." are not Exist");
      }
    } else {
      echo("Empty Binary Tree");
    }
  }
  public
  function push($node) {
    $new_node = new Stack($node);
    $new_node->next = $this->top;
    $this->top = $new_node;
  }
  public
  function pop() {
    if ($this->top != null) {
      $remove = $this->top;
      $this->top = $this->top->next;
      $remove->next = null;
      $remove->element = null;
      $remove = null;
    }
  }
}

function main() {
  $obj = new BinaryTree();


  /* Make A Binary Tree
  -----------------------
         10
       /    \
      2      5
     / \    /  \
    1   3  7    2
       /    \
      9      -4
  */
  $obj->root = new Node(10);
  $obj->root->left = new Node(2);
  $obj->root->right = new Node(5);
  $obj->root->right->right = new Node(2);
  $obj->root->right->left = new Node(7);
  $obj->root->left->left = new Node(1);
  $obj->root->left->right = new Node(3);
  $obj->root->left->right->left = new Node(9);
  $obj->root->right->left->right = new Node(-4);
  $obj->preorder($obj->root);
  echo ("\n");
  $obj->changePath($obj->root, 9);
  $obj->preorder($obj->root);
}
main();

Output

  10  2  1  3  9  5  7  -4  2
  9  3  1  2  10  5  7  -4  2
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment