Binary Search Tree with In Order Traversal implementation in Java
This class is a complete class you can utilize out of the box for your applications.
Node class can be modified to suit your needs.
Node class can be modified to suit your needs.
class BinaryTreeSearch{ public enum State{ Visited, Unvisited,Visiting; } //this is the Node used in the tree static class Node{ private int data; private Node left; private Node right; public Node(int data){ this.data = data; left = null; right = null; } public void setLeft(Node left){ this.left = left; } public void setRight(Node right){ this.right = right; } public Node getLeft(){ return this.left; } public Node getRight(){ return this.right; } public int getData(){ return this.data; } public boolean equals(Node n){ if(this.data ==(int) n.getData()) return true; else return false; } } public static void main(String[] args){ BinaryTreeSearch bts = new BinaryTreeSearch(); bts.run(); } //execute the test case public void run(){ Node root = new Node(10); insert(root,new Node(20)); insert(root,new Node(5)); insert(root,new Node(4)); insert(root,new Node(5)); insert(root,new Node(15)); inOrderTraverse(root); System.out.println("\n" + binarySearch(root,new Node(10))); } // insert a node to the binary search tree public void insert(Node root, Node n){ if(root == null|| n == null) return; if(root.getData() > n.getData()){ if(root.getLeft() == null){ root.setLeft(n); System.out.println("Added node to left of "+root.getData()+" of value "+n.getData()); }else{ insert(root.getLeft(),n); } }else if(root.getData() < n.getData()){ if(root.getRight() == null){ root.setRight(n); System.out.println("Added node to Right of "+root.getData()+" of value "+n.getData()); }else{ insert(root.getRight(),n); } } } //in-order Traversal public void inOrderTraverse(Node root){ if(root != null){ inOrderTraverse(root.getLeft()); System.out.print(" "+root.getData()); inOrderTraverse(root.getRight()); } } //binary search public boolean binarySearch(Node root,Node n){ if(root == null || n == null) { return false; } System.out.println(" Testing out "+root.getData()+" for value "+n.getData()); if(root.getData() > n.getData()){ return binarySearch(root.getLeft(),n); }else if(root.getData() < n.getData()){ return binarySearch(root.getRight(),n); } return true; } }
You're welcome.
ReplyDeletegreat work
ReplyDeleteThis comment has been removed by the author.
ReplyDelete//binary search
ReplyDeletepublic boolean binarySearch(Node root,Node n){
if(root == null || n == null) {
return false;
}
System.out.println(" Testing out "+root.getData()+" for value "+n.getData());
if(root.getData() > n.getData()){
return binarySearch(root.getLeft(),n);
}else if(root.getData() < n.getData()){
return binarySearch(root.getRight(),n);
}
return true;
}
I think this particular code is incorrect and will always return true even for the values not present in the BST. The correct implement should have either "false" or "true" be returned something like this
private boolean binarySearch(Node root, Node node) {
if(root == null || node == null)
return false;
else{
if(root.getData() == node.getData())
return true;
else if(root.getData() > node.getData())
return binarySearch(root.left, node);
else
return binarySearch(root.right, node);
}
}
This comment has been removed by the author.
DeleteGreat Job !
DeleteJust a small change you might wanna make to the above code as even for the non-existing values, binarySearch() still returns a 'true' value.
One more verification step to verify
if(root.getData() == n.getData())
return true;
No Man...
ReplyDeletecode of binarySearch(...) is correct and work well...
Thanks
Hi.. can you show how a delete would work as well please?
ReplyDeleteThanks .. Great work..:D
ReplyDelete