In this post, We will learn How to perform search operation in a binary search tree?
The Search Operation in BST:
- If Tree is Empty then search key won’t find then return false
- If the key equals to root node that means key found then return true
- If the search key is less than the root Node value then search key in left subtree if found than return true
- If the search key is bigger than the root Node value then search key in right subtree if found than return true
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
/** * Return whether key is in the tree rooted at node * @param node tree * @param key value need to search * @return true if key found else return false */ private static <T extends Comparable<? super T>> boolean contains(Node<T> node, T key) { //if tree in Empty if (node == null) { return false; } //If key is find at root node else if (key.compareTo(node.data) == 0) { return true; } //Search key in left subtree else if (key.compareTo(node.data) < 0) { return contains(node.left, key); } else { //Search key in right subtree // k.compareTo(t.key) > 0 return contains(node.right, key); } } |
Complete Souce code:
BinaryTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
package com.kkjavatutorials.tree; public class BinaryTree<E extends Comparable<? super E>> { //Root of Binary Tree private Node<E> root; /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for preOrder Processing * in BST * @param root Node */ public void preOrder(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } } /** * Insert operation in binary search tree * @param data to insert */ public void insert(E data) { root = insert(root, data); } private static <T extends Comparable<? super T>> Node<T> insert(Node<T> node, T data) { if (node == null) { node = new Node<T>(data); } else if (data.compareTo(node.data) < 0) { node.left = insert(node.left, data); } else if (data.compareTo(node.data) > 0) { node.right = insert(node.right, data); } return node; } /** * Return whether Tree contain key in BST * @param key searching value * @return true if key found else return false */ public boolean find(E key) { return contains(root, key); } /** * Return whether key is in the tree rooted at node * @param node tree * @param key value need to search * @return true if key found else return false */ private static <T extends Comparable<? super T>> boolean contains(Node<T> node, T key) { //if tree in Empty if (node == null) { return false; } //If key is find at root node else if (key.compareTo(node.data) == 0) { return true; } //Search key in left subtree else if (key.compareTo(node.data) < 0) { return contains(node.left, key); } else { //Search key in right subtree // k.compareTo(t.key) > 0 return contains(node.right, key); } } public Node<E> getRoot() { return root; } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
package com.kkjavatutorials.client; import java.util.Scanner; import com.kkjavatutorials.tree.BinaryTree; /** * Client Program to test insert operation in Binary Tree * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); binaryTree.insert(10); binaryTree.insert(15); binaryTree.insert(5); binaryTree.insert(40); binaryTree.insert(80); binaryTree.insert(50); System.out.println("Original Binary Search Tree in preOrder processing.."); //Call for preOrder processing binaryTree.preOrder(binaryTree.getRoot()); System.out.println(); Scanner scanner = null; try { System.out.println("Enter key which you want to search:"); scanner = new Scanner(System.in); int searchKey = scanner.nextInt(); boolean find = binaryTree.find(searchKey); if(find) { System.out.println("Seach Key :"+searchKey+" found!!"); }else { System.out.println("Seach Key :"+searchKey+" not found!!"); } } catch (Exception e) { e.printStackTrace(); } } } |
The Input/output of This Program:
Original Binary Search Tree in preOrder processing..
10 5 15 40 80 50
Enter key which you want to search:
40
Seach Key :40 found!!
Original Binary Search Tree in preOrder processing..
10 5 15 40 80 50
Enter key which you want to search:
100
Seach Key :100 not found!!
You May Also Like:
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
That’s all about How to perform search operation in a binary search tree?
If you have any feedback or suggestion please feel free to drop in below comment box.