ISourceCode

Make the frequent cases fast and the rare case correct

Binary Search Tree (BST) – Implementation to Insert a node , delete a node , search a node and display the tree

In the article we see the implementation of a Binary search tree

A BST has the following three properties

# The left subtree of a node contains only nodes with keys less than the node’s key.
# The right subtree of a node contains only nodes with keys greater than the node’s key.
# Both the left and right subtrees must also be binary search trees

The implementation deals with creating a BST, inserting a node into the tree, searching a node and deleting the node.

Whenever a operation is carried out it the BST must still hold the 3 properties mentioned above.

A stack has been implemented using linked lists to demonstrate a displayTree() function which visualizes the tree in the output.

We could use generics to implement the stack, tree etc but i preferred to implement in detail to demonstrate the use of data structures instead of abstracting the ideas.

//@AUTHOR : CHINMAY LOKESH

import java.io.*;
import java.util.*;

class Node
{
	public int item;
	public Node leftChild;
	public Node rightChild;
	public void displayNode()
	{
		System.out.print("[");
		System.out.print(item);
		System.out.print("]");
	}
}
class StackNode
{
	public Node item;
	public StackNode next;
	public StackNode(Node val)
	{
		item = val;
	}

}
class LinkedListStack
{
	private StackNode first;
	public LinkedListStack()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(Node key)//inserts at beginning of list
	{
		StackNode newLLNode = new StackNode(key);
		newLLNode.next = first;
		first = newLLNode;
	}
	public Node delete()//deletes at beginning of list
	{
		StackNode temp = first;
		first = first.next;
		return temp.item;
	}
}
class Stack
{
	private LinkedListStack listObj;
	public Stack()
	{
		listObj = new LinkedListStack();
	}
	public void push(Node num)
	{
		listObj.insert(num);
	}
	public Node pop()
	{
		return listObj.delete();
	}
	public boolean isEmpty()
	{
		return listObj.isEmpty();
	}
}

class Tree
{
	private Node root;
	public Tree()
	{ root = null; }
	public Node find(int val)
	{
		Node current = root;
		while(current.item != val)
		{
			if(val < current.item)
				current = current.leftChild;
			else
				current = current.rightChild;
			if(current == null)
				return null;
		}
		return current;
	} 
	public void insert(int id)
	{
		Node newNode = new Node();
		newNode.item = id;
		if(root==null)
			root = newNode;
		else
		{
			Node current = root;
			Node parent;
			while(true)
			{
				parent = current;
				if(id < current.item)
				{
					current = current.leftChild;
					if(current == null)
					{
						parent.leftChild = newNode;
						return;
					}
				} 
				else
				{
					current = current.rightChild;
					if(current == null) 
					{
						parent.rightChild = newNode;
						return;
					}
				} 
			} 
		} 
	} 
	public boolean delete(int val) 
	{
		Node current = root;
		Node parent = root;
		boolean isLeftChild = true;
		while(current.item != val)
		{
			parent = current;
			if(val < current.item)
			{	
				isLeftChild = true;
				current = current.leftChild;
			}
			else
			{
				isLeftChild = false;
				current = current.rightChild;
			}
			if(current == null)
				return false;

		} 
		if(current.leftChild==null && current.rightChild==null)
		{
			if(current == root)
				root = null;
			else if(isLeftChild)
				parent.leftChild = null;
			else
				parent.rightChild = null;
		}
		else if(current.rightChild==null)
		{
			if(current == root)
				root = current.leftChild;
			else if(isLeftChild)
				parent.leftChild = current.leftChild;
			else
				parent.rightChild = current.leftChild;
		}
		else if(current.leftChild==null)
		{
			if(current == root)
				root = current.rightChild;
			else if(isLeftChild)
				parent.leftChild = current.rightChild;
			else
				parent.rightChild = current.rightChild;
		}
		else 
		{
			Node successor = findSuccessor(current);
			if(current == root)
				root = successor;
			else if(isLeftChild)
				parent.leftChild = successor;
			else
				parent.rightChild = successor;
			successor.leftChild = current.leftChild;
		} 
		return true;
	} 
	private Node findSuccessor(Node delNode)
	{
		Node successorParent = delNode;	
		Node successor = delNode;
		Node current = delNode.rightChild;
		while(current != null)
		{
			successorParent = successor;	
			successor = current;
			current = current.leftChild;
		}
		if(successor != delNode.rightChild)
		{
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		return successor;
	}
	public void displayTree()
	{
		Stack globalStack = new Stack();
		globalStack.push(root);	
		int emptyLeaf = 32;
		boolean isRowEmpty = false;
		System.out.println("****......................................................****");
		while(isRowEmpty==false)
		{

			Stack localStack = new Stack();
			isRowEmpty = true;
			for(int j=0; j<emptyLeaf; j++)
				System.out.print(' ');
			while(globalStack.isEmpty()==false)
			{
				Node temp = globalStack.pop();
				if(temp != null)
				{
					System.out.print(temp.item);
					localStack.push(temp.leftChild);
					localStack.push(temp.rightChild);
					if(temp.leftChild != null ||temp.rightChild != null)
						isRowEmpty = false;
				}
				else
				{
					System.out.print("--");
					localStack.push(null);
					localStack.push(null);
				}
				for(int j=0; j<emptyLeaf*2-2; j++)
					System.out.print(' ');
			}
			System.out.println();
			emptyLeaf /= 2;
			while(localStack.isEmpty()==false)
				globalStack.push( localStack.pop() );
		}
	System.out.println("****......................................................****");
	} 
} 
class TreeBasic
{

	public static void main(String[] args) throws IOException
	{
		int value;
		Tree theTree = new Tree();
		theTree.insert(42);
		theTree.insert(25);
		theTree.insert(65);
		theTree.insert(12);
		theTree.insert(37);
		theTree.insert(13);
		theTree.insert(30);
		theTree.insert(43);
		theTree.insert(87);
		theTree.insert(99);
		theTree.insert(9);

		System.out.println("Displaying the tree");
		theTree.displayTree();

		System.out.println("Inserting 23 into the tree");
		theTree.insert(23);

		theTree.displayTree();

		System.out.println("Finding 65 in the tree");
		Node found = theTree.find(65);
		if(found != null)
		{
			System.out.print("Found: ");
			found.displayNode();
			System.out.println("\n");
		}
		else
			System.out.println("Could not find the node");

		System.out.println("Deleting 87 from the tree");
		boolean ifDelete1 = theTree.delete(87);
		if(ifDelete1)
			System.out.println("Deleted 87");
		else
			System.out.println("Could not delete ");
	
		theTree.displayTree();

		System.out.println("Deleting 25 from the tree");
		boolean ifDelete2 = theTree.delete(25);
		if(ifDelete2)
			System.out.println("Deleted 25");
		else
			System.out.println("Could not delete ");

		theTree.displayTree();

			
	} 
} 

OUTPUT:

~/Tree$ java TreeBasic 
Displaying the tree
****......................................................****
                                42                                                              
                25                              65                              
        12              37              43              87              
    9      13      30      --      --      --      --      99      
****......................................................****
Inserting 23 into the tree
****......................................................****
                                42                                                              
                25                              65                              
        12              37              43              87              
    9      13      30      --      --      --      --      99      
  --  --  --  23  --  --  --  --  --  --  --  --  --  --  --  --  
****......................................................****
Finding 65 in the tree
Found: [65]

Deleting 87 from the tree
Deleted 87
****......................................................****
                                42                                                              
                25                              65                              
        12              37              43              99              
    9      13      30      --      --      --      --      --      
  --  --  --  23  --  --  --  --  --  --  --  --  --  --  --  --  
****......................................................****
Deleting 25 from the tree
Deleted 25
****......................................................****
                                42                                                              
                30                              65                              
        12              37              43              99              
    9      13      --      --      --      --      --      --      
  --  --  --  23  --  --  --  --  --  --  --  --  --  --  --  --  
****......................................................****

3 responses to “Binary Search Tree (BST) – Implementation to Insert a node , delete a node , search a node and display the tree

  1. sanstechbytes November 26, 2011 at 10:48 am

    Good demonstration of the BST!

  2. Chung Tet Kun March 17, 2013 at 8:35 pm

    thanks for sharing the great code!

  3. karen Grace September 13, 2013 at 1:30 am

    thank you!!! this tutorial helped me a lot!

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

%d bloggers like this: