Posted on by Kalkicode
Code Binary Tree

# 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.

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;

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

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

## 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.

Categories
Relative Post