Binary search tree. Lookup operation
Searching for a value in a BST is very similar to add operation. Search algorithm traverses the tree "in-depth", choosing appropriate way to go, following binary search tree property and compares value of each visited node with the one, we are looking for. Algorithm stops in two cases:
- a node with necessary value is found;
- algorithm has no way to go.
Search algorithm in detail
Now, let's see more detailed description of the search algorithm. Like an add operation, and almost every operation on BST, search algorithm utilizes recursion. Starting from the root,
- check, whether value in current node and searched value are equal. If so, value is found. Otherwise,
- if searched value is less, than the node's value:
- if current node has no left child, searched value doesn't exist in the BST;
- otherwise, handle the left child with the same algorithm.
- if a new value is greater, than the node's value:
- if current node has no right child, searched value doesn't exist in the BST;
- otherwise, handle the right child with the same algorithm.
Example
Search for 3 in the tree, shown above.
Code snippets
As in add operation, check first if root exists. If not, tree is empty, and, therefore, searched value doesn't exist in the tree. This check can be done in the BinarySearchTree class. Principal algorithm is implemented in the BSTNode class.
Java
public class BinarySearchTree {
…
public boolean search(int value) {
if (root == null)
return false;
else
return root.search(value);
}
}
public class BSTNode {
…
public boolean search(int value) {
if (value == this.value)
return true;
else if (value < this.value) {
if (left == null)
return false;
else
return left.search(value);
} else if (value > this.value) {
if (right == null)
return false;
else
return right.search(value);
}
return false;
}
}
C++
bool BinarySearchTree::search(int value) {
if (root == NULL)
return false;
else
return root->search(value);
}
bool BSTNode::search(int value) {
if (value == this->value)
return true;
else if (value < this->value) {
if (left == NULL)
return false;
else
return left->search(value);
} else if (value > this->value) {
if (right == NULL)
return false;
else
return right->search(value);
}
return false;
}
Visualizers
Recommended books
- Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
- Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
- Robert Lafore. Data Structures and Algorithms in Java. (Practice)
- Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)
| Previous: Add operation on BST | Next: Remove operation on BST |
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!