## 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;
}

}

```

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;

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.
Saurabh Srivastava
MaxMunus
E-mail: saurabh@maxmunus.com
Skype id: saurabhmaxmunus
Ph:+91 8553576305 / 080 - 41103383
http://www.maxmunus.com/

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

hadoop training in bangalore

4. Great message and nice information its very useful to read your blog. We provide best Digital Transformation Services

5. Very nice article and very nice explanation about binary tree. Thanks for sharing such nice article, keep on up dating such good articles.

Austere Technologies | Best Cloud Solution services

6. wow...nice blog, very help full information. Thanks for sharing.

NO.1 APP DEVELOPMENT SERVICES | MASSIL TECHNOLOGIES

7. Very good informative article. Thanks for sharing such nice article, keep on up dating such good articles.

NO.1 CLOUD SERVICES | ORACLE CLOUD SERVICES FOR APPLICATION DEVELOPMENT

8. REALLY VERY EXCELLENT INFORMATION. I AM VERY GLAD TO SEE YOUR BLOG FOR THIS INFORMATION. THANKS FOR SHARING. KEEP UPDATING.

NO.1 IOT Services | INTERNET OF THINGS | Best IOT Services |

9. It's very informative blog. Thanks for sharing.

NO.1 Mobile APPilication DEVELOPMENT SERVICES | MASSIL TECHNOLOGIES

10. What an excellent information. Thanks for sharing.

Best Mobility Services | Austere Technologies

11. Great information, keep sharing.

Best IT Security Services | Austere Technologies

12. Wonderful Article.The information you have delivered in this post was very nice.keep updating.
Summer Courses in Chennai | Summer Classes in Pallikaranai | Summer Camp Training in Pallikaranai

13. Nice blog with excellent information. Thank you, keep sharing.

Join in Avinash College Of Commerce for Best career in commerce

14. Wow...What an excellent informative blog, really helpful. Thank you.

Software Testing Services | Austere Technology

15. Great article, really very helpful content you made. Thank you, keep sharing.

chartered accountant | Avinash college of commerce

16. Nice blog with excellent information. Thank you, keep sharing.

chartered accountant course in Hyderabad | Avinash college of commerce

17. This is a really great informative blog. Keep Sharing.

Best Degree Colleges Hyderabad | Avinash College of Commerce

18. Hi Thanks for the nice information its very useful to read your blog. We provide best Block Chain Services

19. Thank you for sharing this valuable information. But get out of this busy life and find some peace with a beautiful trip book Andaman family tour packages

20. Thank you for sharing this valuable information. But get out this busy life and find some peace with a beautiful trip. book ANDAMAN BUDGET PACKAGES @ 4999/-

21. Thank you for sharing this valuable information. But get out this busy life and find some peace with a beautiful trip. book Andaman Tourism

22. Thank you for sharing this valuable information. But get out this busy life and find some peace with a beautiful trip. book Best Travel Agency In India

23. Hi Thanks for the nice information its very useful to read your blog. We provide best Find All Isfs Courses

24. Hi Thanks for the nice information its very useful to read your blog. We provide best Massil Technologies

25. Best informative blog. Thank you.

cima courses in hyderabad | ISFS

26. Excellent informative blog, keep for sharing.

Best System Integration services | Massil Technologies

27. Excellent informative blog, keep sharing.

CA institute in hyderabad | Avinash College of Commerce

28. Excellent informative blog, Thanks for sharing.

cs institutes in hyderabad | Avinash College of Commerce

29. Thanks for the nice information and also it's very inspirational and Thanks for the detailed explanation. Really useful. Keep sharing more. Regards. Click Here for Commerce College in Hyderabad

30. Wow...What an excellent informative blog, really helpful. Thank you. Best Oracle DBA Course Training| orskl