Created
December 18, 2017 16:45
-
-
Save rishi93/6c2a9fb4cdafff0ba99766f232d06388 to your computer and use it in GitHub Desktop.
Binary search tree (Implementation in Java)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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