Search in Binary Search Tree

Tags: , ,

Search in Binary Search Tree

In previous post Binary Search Tree : Insertion we discussed basics about binary search tree and learned how to insert a node in BST.  One thing binary search tree data structure is known for is fast search.  Let’s discuss how to search in binary search tree? Given an key and BST, check if key exists in BST or not. For example :In below tree, if searched key is 6, answer is True and if searched key is 8, answer should be False.

search in binary search tree

What is brute force solution for search? We go through all nodes of tree and check if the value of node is what we are looking for. If yes, then return True. If we scanned all nodes and no node has key, returned false. Complexity of this search will O(n) where n is number of nodes in BST.

Search in binary search tree : Line of thought

Can we do better than linear complexity?  In brute force approach, we did not use binary search tree property that all nodes in left subtree are less than root and all nodes in right subtree are greater than root. If value in root node is greater than value being searched, what does it tell about other nodes? If value in root node is greater than key, we can guarantee that all nodes on the right subtree will be less than searched value.
What if value at root node is less than key? In that case we know all nodes on left subtree must be less than searched value.

In any case, we can discard either left or right subtree and look for element in other subtree. Sounds familiar to Binary search algorithm ?

In binary search algorithm, we can again split the remaining subarray into half, can we do in BST? Of course. Since all nodes follow the BST property, we can always split on each node, discarding one subtree and search in other based on relationship between value in value of root node and searched value. This gives us hint about recursive implementation.

If value at root is equal to searched value, return true. If we find root node as null, there is no such key in tree.

Search in binary search tree : Algorithm

  1. While there is a node in binary search tree
    • If root.value ==  key return true
    • If root.value > key, search in left subtree, root = root.left, go to step 1.
    • If root.value < key, search in right subtree, root = root.right, go to step 1.
  2. If there is no node in tree, return false.

Let’s take an example and see how this algorithm works? Given below BST, find key 6.

search in binary search tree

First of all, there are nodes in BST, hence check if root.value is equal to key? In this case (10) is greater than (6). So all nodes on right subtree of node(10) will be greater than (6), hence discard right subtree and focus on left subtree.

Now, the root node of left subtree is node(5). There are nodes in tree hence, check if root.value is equal to key. Here, (5) is less than key(6), so all nodes on left subtree will be less than key(6). Discard left subtree and focus on right subtree of node(5).

There are nodes in subtree, so check again root.value == key. Now root.value is equal to key, return true.

Can you find the flow to find key 9 in the same tree?

Search in binary search tree : Recursive implementation

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private boolean searchRecursive(Node root, int value){
        if(root == null) return false;

        if(root.value == value) return true;
        if(root.value > value ) return searchRecursive(root.left, value);
        if(root.value < value ) return searchRecursive(root.right, value);

        return false;
    }

    public boolean search(int value){
        return this.searchRecursive(this.root, value);
    }
}

Test code

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        boolean isFound = binarySearchTree.search(15);
        System.out.print( isFound ? "Element found" : "Element not found");

    }
}

Complexity of search in binary search is very tricky question.  It’s common mistake to think that worst case complexity of search in BST is O(log n) same as binary search algorithm. However, this is true only when BST is balanced tree and at every node, we can discard half of the nodes. What is all nodes of tree are on one subtree only as show below. In that case worst complexity of search will be O(n).

Please share if there is something wrong or missing. If you want to share your knowledge with thousands of learners across the world, please reach out to us on communication@algorithmsandme.com