Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

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,

  1. check, whether value in current node and searched value are equal. If so, value is found. Otherwise,
  2. 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.
  3. 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.
Just before code snippets, let us have a look on the example, demonstrating searching for a value in the binary search tree.

Example

Search for 3 in the tree, shown above.

BST search example, step 1
BST search example, step 2
BST search example, step 3

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

  1. Binary Search Tree (Search) in Java Applets Centre

Recommended books

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
  3. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  4. Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)

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!

Partners Ads        smooth masonry paint        

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: