Search Operation in Binary Search Tree

Problem statement: The root of a binary search tree and key k is given. Write a program to search key k into the BST. If key k is present, return a pointer to the node containing key k. Otherwise, return NULL.

Searching in a BST using recursion

Solution idea

A binary search tree is a sorted binary tree, where the root->key is greater than or equal to the keys of all nodes in the left subtree and less than or equal to the keys of all nodes in the right subtree. So we can apply the divide and conquer idea similar to binary search, i.e. we compare root->key with k and divide the searching problem into one smaller sub-problem of searching either left or right sub-tree.

As we search in a BST, the size of search space reduces max by half (when the tree is balanced) but at least by one (when the tree is skewed). The search process stops either when a node containing the search key is found or we reach one of the NULL links.

 search in bst example

Solution steps

The recursive algorithm to search for a key in a BST follows a simple recursive structure: if key k is equal to the root->key, we have a search hit. Otherwise, we search recursively in the appropriate subtree.

Suppose we define a function BSTSearch(root, k), which takes root and search key k as an input.

  • If (root->key == k), return root.
  • If (root->key > k): All keys in the right subtree are greater than root->key, so we search recursively in the left subtree by calling the same function for root->left, i.e. BSTSearch(root->left, k).
  • If (root->key < k): All keys in the left subtree are less than root->key, so we search recursively in the right subtree by calling the same function for root->right, i.e. BSTSearch(root->right, k).

Solution pseudocode

BSTSearch(root, k)
    if root is null or root.key == k
        return root

    if root.key > k
        return BSTSearch(root.left, k)
    else
        return BSTSearch(root.right, k)

Searching in BST using iteration

Solution idea

We can iteratively rewrite the above procedure by unrolling the recursion into a while loop. We start searching from the root and traverse a path iteratively downward. For each node x in the path, we compare k with x->key. If both are equal, the search is successful. If k is smaller than the x->key, we search iteratively in the left subtree of x. Similarly, if k is larger than the x->key, we search iteratively in the right subtree.

Solution steps

We run a while loop till root->key != k or root != NULL. 

  • If root->key > k, set root = root->left.
  • If root->key < k, set root = root->right.
  • If the loop exits due to root == NULL, there is a search miss.
  • If the loop exit due to root->key == k, there is a search hit.
BSTSearch(root, k)
    while root is not null and root.key != k
        if root.key > k
            root = root.left
        else
            root = root.right

    return root

Time complexity analysis

Nodes encountered during the recursion or iteration generate a path from the root node. If the search is successful, path terminates at the node containing the key. Otherwise, it will traverse a path from the root node to one of the NULL links. So search method will perform one comparison at each level. In the worst case, total number of comparison operations = tree height (h). Time complexity of searching in BST = Height of BST * O(1) = h * O(1) = O(h).

When BST is balanced, both the left and right subtree will be the same size (n/2), and the height of BST will be O(logn). So time complexity of searching in a balanced BST = O(logn)

When BST is completely unbalanced, the BST will be a linear chain of nodes (one node at each level), and the height of such BST is O(n). So time complexity of searching in an unbalanced BST = O(n)

Space complexity analysis

We use constant extra memory in iterative implementation, so the space complexity of iterative search operation in BST = O(1). There will be one recursive call at each tree level in the recursive implementation. So space complexity depends on the size of the recursion call stack, which is equal to the tree's height. so space complexity of recursive search operation in BST = O(h)

  • For balanced BST, space complexity = O(logn).
  • For a completely unbalanced BST, space complexity = O(n).

Enjoy learning, enjoy algorithms!

Find us on:

Self-paced Courses and Blogs