...

/

Search in Binary Search Trees (Implementation)

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.

  1. Start from Root.
  2. 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.
  3. Keep on doing the above step until you either find a node with that value or reach a leaf node—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 {
//Variables
private Node root;
//Getter for Root
public 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 null
public Node search(int value) {
if (isEmpty()) return null; // if tree is empty simply return null
Node currentNode = this.root;
while (currentNode != null) {
if (currentNode.getData() == value) return currentNode; // compare data from current node
if (currentNode.getData() > value) //if data from current node is greater than value
currentNode = currentNode.getLeftChild(); // then move towards left subtree
else
currentNode = 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 BST
public Node recursive_insert(Node currentNode, int value) {
//Base Case
if (currentNode == null) {
return new Node(value);
}
if (value < currentNode.getData()) {
//Iterate left sub-tree
currentNode.setLeftChild(recursive_insert(currentNode.getLeftChild(), value));
} else if (value > currentNode.getData()) {
//Iterate right sub-tree
currentNode.setRightChild(recursive_insert(currentNode.getRightChild(), value));
} else {
// value already exists
return currentNode;
}
return currentNode;
}
//Function to call recursive insert
public boolean add(int value) {
root = recursive_insert(this.root, value);
return true;
}
//Function to check if Tree is empty or not
public boolean isEmpty() {
return root == null; //if root is null then it means Tree is empty
}
//Just for Testing purpose
public 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 ...