Binary Search Trees : Insertion and Reversal

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s