Search in Binary Search Trees (Implementation)
This lesson is about Searching in a Binary Search Tree, and how to implement searching functionality in Java.
Introduction
In this lesson, we are going to implement the Search functionality by using the BST class. The following are the steps that we perform to search for an element in BST.
- Start from Root.
- If the value is less than the current node value, then traverse the left sub-tree; if it is more, then traverse the right sub-tree.
- Keep on doing the above step until you either find a
node
with that value or reach a leafnode
—in which case the value doesn’t exist in the Binary Search Tree.
Iterative Search Implementation
Press + to interact
main.java
Node.java
binarySearchTree.java
class binarySearchTree {//Variablesprivate Node root;//Getter for Rootpublic Node getRoot() {return root;}public void setRoot(Node root) {this.root = root;}//Searches value in BST//Either returns the Node with that value or return nullpublic Node search(int value) {if (isEmpty()) return null; // if tree is empty simply return nullNode currentNode = this.root;while (currentNode != null) {if (currentNode.getData() == value) return currentNode; // compare data from current nodeif (currentNode.getData() > value) //if data from current node is greater than valuecurrentNode = currentNode.getLeftChild(); // then move towards left subtreeelsecurrentNode = currentNode.getRightChild(); //else move towards right subtree}System.out.println(value + " Not found in the Tree!");return null;}//Recursive function to insert a value in BSTpublic Node recursive_insert(Node currentNode, int value) {//Base Caseif (currentNode == null) {return new Node(value);}if (value < currentNode.getData()) {//Iterate left sub-treecurrentNode.setLeftChild(recursive_insert(currentNode.getLeftChild(), value));} else if (value > currentNode.getData()) {//Iterate right sub-treecurrentNode.setRightChild(recursive_insert(currentNode.getRightChild(), value));} else {// value already existsreturn currentNode;}return currentNode;}//Function to call recursive insertpublic boolean add(int value) {root = recursive_insert(this.root, value);return true;}//Function to check if Tree is empty or notpublic boolean isEmpty() {return root == null; //if root is null then it means Tree is empty}//Just for Testing purposepublic void printTree(Node current) {if (current == null) return;System.out.print(current.getData() + ",");printTree(current.getLeftChild());printTree(current.getRightChild());}}
Explanation
The search()
function is implemented in lines 17-35 in binarySearchTree.java
file. We take advantage of the property of BST in this function. If the given value is less than the value of currentNode
then we only search in the left sub-tree of the currentNode
, or else we search in the right. We repeat this until either the node is ...