Reverse the path from given node to root node

Reverse the path values form given node

Here given code implementation process.

/*
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


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







© 2021, kalkicode.com, All rights reserved