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