Recently I was asked by a fellow colleague if I knew how to reverse a binary search tree in Java. I knew the process and had an idea about binary search trees but I was really unable to write a code for that[it was a time limit question]. So after looking at a few articles and understanding the reversal algorithm, I was able to do it with recursion.

So lets recall once what is it we are talking about:

## What is a Binary Search Tree (BST)?

Binary Search Tree (BST) is a binary tree data structure with a special feature where in the value store at each node is greater than or equal to the value stored at its left sub child and lesser than the value stored at its right sub child.

## What is the solution ?

So, first of all I create a Node type of class

class Node

{

Node left;

Node right;

int value;

Node(int value)

{

this.value=value;

}

}

Now I create a new class in which I define an insert , print and reversal method as :

public void insert(Node node,int value)

{

if (value < node.value) { if (node.left !=null) { insert(node.left,value); } else { System.out.println(" Inserted " + value + " to left of node " + node.value); node.left=new Node(value); } } else if (value > node.value) {

if (node.right!=null) {

insert(node.right,value);

}

else {

System.out.println(" Inserted " + value + "to right of node " + node.value);

node.right=new Node(value);

}

}

}

public void printInOrder(Node node) {

if (node != null) {

printInOrder(node.left);

System.out.println(" Traversed " + node.value);

printInOrder(node.right);

}

}

public void reverse(Node node)

{

Node tmp;

if (node!=null) {

tmp=node.left;

node.left=node.right;

node.right=tmp;

reverse(node.left);

reverse(node.right);

}

}

And finally comes the main method as:

Node rootnode= new Node(25);

System.out.println(rootnode.value);

insert(rootnode, 11);

insert(rootnode, 15);

insert(rootnode, 16);

insert(rootnode, 23);

insert(rootnode, 79);

System.out.println("Traversing tree in order");

printInOrder(rootnode);

System.out.println("Traversing tree in reverse order");

reverse(rootnode);

printInOrder(rootnode);

So, finally I could obtain the reversal of binary tree with the help of our valuable resources available in internet. 🙂