Tuesday, August 2, 2011

Binary Tree Implementation in JAVA

Before we proceed with the Binary tree implementation, let us first understand the building elements - nodes. Lets define the data structure for a Node.

Every node is left or right child to parent on the basis of its value compared to parent. So we need some way to compare objects. Thus, Data type has to be either primitive OR should have implemented comparable.

Taking the generalized approach - I'll proceed with comparable type. i'll explain Binary Search Tree - Search, Binary Search Tree - Insertion, Binary Search Tree - Find Minimum, Binary Search Tree - Remove minimum, Binary Search Tree - Remove a particular node.

The comments in the code explain the details.


package main.java.algo.datastructures.binarytree;

/*** 

                 5

           /           \

         2               8

       /   \           /   \

     1       4       7       9

   / \      /       /

0   1.5     3       6


 ***/


// name of class is BT but implementations are for BST

public class BinaryTrees {

	Node root = null;

	public BinaryTrees() {
		root = new Node();
	}
	
	public Node getRoot() {
		return root;
	}

	public void makeEmpty() {
		root = null;
	}

	public boolean isEmpty() {
		return root == null;
	}

	/**************************** Search ****************************/

	public boolean lookup(Object obj) {
		return lookup(root, obj);
	}

	public boolean lookup(Node node, Object obj) {

		// if root is null - means tree is empty
		// node.right or node.left is null - means node was the leaf. node.right
		// or node.left was not existing.
		if (node == null)
			return false;

		// using compareTo (since object implements comparable)
		// if data was primitive, we could have used a< b kind of comparisons

		// if the object is equal to the current node - is success.
		else if (node.data.compareTo(obj) == 0)
			return true;

		// if the current node is greater than object, object should be looked
		// in the left subtree
		else if (node.data.compareTo(obj) > 0)
			return lookup(node.left, obj);

		// if the current node is less than object, object should be looked in
		// the right subtree
		else
			return lookup(node.right, obj);
	}

	/**************************** Insert ****************************/

	public Node insert(Object obj) throws Exception {
		return insert(root, obj);
	}

	/***
	 *** Recursive insert -- given a node pointer, recur down and insert the given
	 *** data into the tree. Returns the new node pointer (the standard way to
	 *** communicate a changed pointer back to the caller).
	 ***/
	
	// In a BST, all values are already ordered - that means, for any node, 
	// left child is always less than the parent and right is greater.
	// This any node node when added - can be added at the end as a LEAF node.

	public Node insert(Node node, Object obj) throws Exception {
		if (node == null)
			node = new Node(obj);
		else if (node.data.compareTo(obj) == 0)
			throw new Exception("Node duplicate");
		else if (node.data.compareTo(obj) > 0)
			node.left = insert(node.left, obj);
		else
			node.right = insert(node.right, obj);
		return node;
	}

	/***
	 *** Earlier I wrote this. But it was wrong. Why?
	 *** 
	 *** I was doing a return. No doubt when it will reach the right position in a
	 *** tree, it will create a new node.But that node has to be node.left or
	 *** node.right of its parent. This pointer connection was not happening with
	 *** below approach.So, the one mentioned above - insert(Node node, Object
	 *** obj) - creates a new and also maintains the pointer connections for newly
	 *** created items.
	 *** 
	 *** public Node insertWrongImplementation (Node node, Object obj) throws
	 *** Exception { if (node == null) return new Node(obj); else
	 *** if(node.data.compareTo(obj) == 0) throw new Exception("Node duplicate");
	 *** else if(node.data.compareTo(obj) > 0) return (insert(node.left, obj));
	 *** else return (insert(node.right, obj)); }
	 ***/
	
	// Also, note here that I am using pointers node.left=... node.right=... 
	// This is also consuming O(n) space complexity. To avoid this, try something like --
	
	public void insertWithLessMemory (Node node, Object obj) throws Exception {
		 if (node.data.compareTo(obj) > 0) {
			 if(node.left == null)
				 node.left = new Node(obj);
			 insertWithLessMemory(node.left, obj); 
		 } else {
			 if(node.right == null)
				 node.right = new Node(obj);
			 insertWithLessMemory(node.right, obj);
		 }
	}

	/**************************** Find Minimum ****************************/
	
	public Node findMinumum() {
		return findMinumum(root);
	}

	public Node findMinumum(Node node) {
		if (node == null)
			return null;
		// we need to check if actually the left most node exists, only then
		// move it to the left
		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

	/**************************** Remove Minimum ****************************/

	// Remove minimum. After removal return the new minimum node.

	public Node removeMinmum() {
		return removeMinmum(root);
	}

	// The below logic works well for the tree on top os this class.
	// But what if the element 0 was not there, 1 had no left child but had only
	// right child 1.5
	// Then this logic breaks
	public Node removeMinmumWrongImplemetation(Node node) {
		if (node == null)
			return null;
		while (node.left.left != null) {
			node = node.left;
		}
		node.left = null;
		return node;
	}
	
	// so this will work now
	public Node removeMinmum2(Node node) {
		if (node == null)
			return null;
		
		while (node.left.left != null) {
			node = node.left;
		}
		
		if(node.left.right != null)
			node.left = node.left.right;
		else
			node.left = null;
		
		return node;
	}

	/*** ******************************************************************

			 5
    		/
		   4
		  /
		 2
		  \
		    3
	
	 ****************************************************************** ***/


	// Note: Whenever nodes are added/removed/rearranged - the node.left, node.right pointer 
	// connections are re-established, so make sure these pointers are also created in add/remove/rearrange
	public Node removeMinmum(Node node) {
		if (node == null)
			return null;
		if (node.left != null) {
			node.left = removeMinmum(node.left);
			return node;
		} else {
			return node.right;
		}
	}

	/**************************** Remove ****************************/

	public Node remove(Object x) {
		return remove(root, x);
	}

	public Node remove(Node node, Object x) {
		if (node == null)
			return null;
		
		//it is important to maintain the pointers node.left = ... node.right = ... 
		//After the node is removed, we need to make sure that pointers are set correct as well.
		else if (node.data.compareTo(x) > 0)
			node.left = remove(node.left, x);
		else if (node.data.compareTo(x) < 0)
			node.right = remove(node.right, x);

		// when the node if found - to be deleted
		else {
			// internal node - with 2 children
			
			// in this case - we don't need to touch the left subtree. in the right tree
			// values increase towards the end. so pick up the least item from
			// right tree. it can be directly replaced with current node. and
			// node.data < node.right.data and node.data > node.left.data will
			// also hold good.
			if (node.left != null && node.right != null) {
				node.data = findMinumum(node.right).data;
				//CHECK IF THIS IS CORRECT
				removeMinmum(node.right);
				//CHECK IF THIS IS CORRECT
				//node.right = removeMinmum(node.right);
			}
			// external node with no or one child.
			
			// in this case - replace current node with right or left child, which ever is present.
			else {
				node = (node.left != null) ? node.left : node.right;
			}
		}
		return node;
	}

	
}

4 comments:

  1. Assuming that the Node class default constructor sets the data/obj to null;
    The constructor of the Binary tree root = new Node(); will set the root(the first value in the tree) to null/0 and there after every element entered will be on the right side;

    ReplyDelete
  2. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in TECHNOLOGY , kindly contact us http://www.maxmunus.com/contact
    MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.
    For Demo Contact us.
    Saurabh Srivastava
    MaxMunus
    E-mail: saurabh@maxmunus.com
    Skype id: saurabhmaxmunus
    Ph:+91 8553576305 / 080 - 41103383
    http://www.maxmunus.com/


    ReplyDelete
  3. Thanks a lot very much for the high quality and results-oriented help. I won’t think twice to endorse your blog post to anybody who wants and needs support

    about this area.
    hadoop training in bangalore

    ReplyDelete