Skip to content

Instantly share code, notes, and snippets.

@rishi93
Created December 18, 2017 16:45
Show Gist options
  • Select an option

  • Save rishi93/6c2a9fb4cdafff0ba99766f232d06388 to your computer and use it in GitHub Desktop.

Select an option

Save rishi93/6c2a9fb4cdafff0ba99766f232d06388 to your computer and use it in GitHub Desktop.
Binary search tree (Implementation in Java)
import java.util.Queue;
import java.util.LinkedList;
class Node{
int data;
Node left, right;
Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree{
Node root;
BinarySearchTree(){
root = null;
}
void printLevelOrder(){
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while(queue.isEmpty() == false){
Node curr = queue.poll();
System.out.print(curr.data + " ");
if(curr.left != null){
queue.add(curr.left);
}
if(curr.right != null){
queue.add(curr.right);
}
}
System.out.println();
}
Node insert(Node curr, int key){
if(curr == null){
curr = new Node(key);
return curr;
}
if(key < curr.data){
curr.left = insert(curr.left, key);
}
else if(key > curr.data){
curr.right = insert(curr.right, key);
}
return curr;
}
boolean search(Node curr, int key){
if(curr == null){
return false;
}
if(curr.data == key){
return true;
}
if(key < curr.data){
return search(curr.left, key);
}
else if(key > curr.data){
return search(curr.right, key);
}
return false;
}
}
public class Test{
public static void main(String[] args){
BinarySearchTree tree = new BinarySearchTree();
tree.root = tree.insert(tree.root, 5);
tree.root = tree.insert(tree.root, 7);
tree.root = tree.insert(tree.root, 3);
tree.root = tree.insert(tree.root, 6);
tree.root = tree.insert(tree.root, 4);
tree.root = tree.insert(tree.root, 2);
tree.root = tree.insert(tree.root, 8);
tree.printLevelOrder();
System.out.println(tree.search(tree.root, 8));
System.out.println(tree.search(tree.root, 9));
System.out.println(tree.search(tree.root, 2));
System.out.println(tree.search(tree.root, 1));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment