Searching in Binary Search Tree (BST)

Last Updated : 21 Nov, 2023

Given a BST, the task is to search a node in this BST.

For searching a value in BST, consider it as a sorted array. Now we can easily perform search operation in BST using Binary Search Algorithm.

Algorithm to search for a key in a given Binary Search Tree:

Let’s say we want to search for the number X, We start at the root. Then:

We compare the value to be searched with the value of the root.
- If it’s equal we are done with the search if it’s smaller we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are smaller and all the elements in the right subtree are larger.
Repeat the above step till no more traversal is possible
If at any iteration, key is found, return True. Else False.

Illustration of searching in a BST:

See the illustration below for a better understanding:

Program to implement search in BST:

C++

// C++ function to search a given key in a given BST
 
#include <iostream>
 
using namespace std;
 
struct node {
    int key;
    struct node *left, *right;
};
 
// A utility function to create a new BST node
struct node* newNode(int item)
{
    struct node* temp
        = new struct node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to insert
// a new node with given key in BST
struct node* insert(struct node* node, int key)
{
    // If the tree is empty, return a new node
    if (node == NULL)
        return newNode(key);
 
    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
 
    // Return the (unchanged) node pointer
    return node;
}
 
// Utility function to search a key in a BST
struct node* search(struct node* root, int key)
{
    // Base Cases: root is null or key is present at root
    if (root == NULL || root->key == key)
        return root;
 
    // Key is greater than root's key
    if (root->key < key)
        return search(root->right, key);
 
    // Key is smaller than root's key
    return search(root->left, key);
}
 
// Driver Code
int main()
{
    struct node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
 
    // Key to be found
    int key = 6;
 
    // Searching in a BST
    if (search(root, key) == NULL)
        cout << key << " not found" << endl;
    else
        cout << key << " found" << endl;
 
    key = 60;
 
    // Searching in a BST
    if (search(root, key) == NULL)
        cout << key << " not found" << endl;
    else
        cout << key << " found" << endl;
    return 0;
}

C

// C function to search a given key in a given BST
 
#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int key;
    struct node *left, *right;
};
 
// A utility function to create a new BST node
struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to insert
// a new node with given key in BST
struct node* insert(struct node* node, int key)
{
    // If the tree is empty, return a new node
    if (node == NULL)
        return newNode(key);
 
    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
 
    // Return the (unchanged) node pointer
    return node;
}
 
// Utility function to search a key in a BST
struct node* search(struct node* root, int key)
{
    // Base Cases: root is null or key is present at root
    if (root == NULL || root->key == key)
        return root;
 
    // Key is greater than root's key
    if (root->key < key)
        return search(root->right, key);
 
    // Key is smaller than root's key
    return search(root->left, key);
}
 
// Driver Code
int main()
{
    struct node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
 
    // Key to be found
    int key = 6;
 
    // Searching in a BST
    if (search(root, key) == NULL)
        printf("%d not found\n", key);
    else
        printf("%d found\n", key);
 
    key = 60;
 
    // Searching in a BST
    if (search(root, key) == NULL)
        printf("%d not found\n", key);
    else
        printf("%d found\n", key);
    return 0;
}

Java

// Java program to search a given key in a given BST
 
class Node {
    int key;
    Node left, right;
 
    public Node(int item) {
        key = item;
        left = right = null;
    }
}
 
class BinarySearchTree {
    Node root;
 
    // Constructor
    BinarySearchTree() {
        root = null;
    }
 
    // A utility function to insert
    // a new node with given key in BST
    Node insert(Node node, int key) {
        // If the tree is empty, return a new node
        if (node == null) {
            node = new Node(key);
            return node;
        }
 
        // Otherwise, recur down the tree
        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
 
        // Return the (unchanged) node pointer
        return node;
    }
 
    // Utility function to search a key in a BST
    Node search(Node root, int key) {
        // Base Cases: root is null or key is present at root
        if (root == null || root.key == key)
            return root;
 
        // Key is greater than root's key
        if (root.key < key)
            return search(root.right, key);
 
        // Key is smaller than root's key
        return search(root.left, key);
    }
 
    // Driver Code
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
 
        // Inserting nodes
        tree.root = tree.insert(tree.root, 50);
        tree.insert(tree.root, 30);
        tree.insert(tree.root, 20);
        tree.insert(tree.root, 40);
        tree.insert(tree.root, 70);
        tree.insert(tree.root, 60);
        tree.insert(tree.root, 80);
 
        // Key to be found
        int key = 6;
 
        // Searching in a BST
        if (tree.search(tree.root, key) == null)
            System.out.println(key + " not found");
        else
            System.out.println(key + " found");
 
        key = 60;
 
        // Searching in a BST
        if (tree.search(tree.root, key) == null)
            System.out.println(key + " not found");
        else
            System.out.println(key + " found");
    }
}

Python3

# Python3 function to search a given key in a given BST
 
class Node:
    # Constructor to create a new node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
# A utility function to insert
# a new node with the given key in BST
def insert(node, key):
    # If the tree is empty, return a new node
    if node is None:
        return Node(key)
 
    # Otherwise, recur down the tree
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
 
    # Return the (unchanged) node pointer
    return node
 
# Utility function to search a key in a BST
def search(root, key):
    # Base Cases: root is null or key is present at root
    if root is None or root.key == key:
        return root
 
    # Key is greater than root's key
    if root.key < key:
        return search(root.right, key)
 
    # Key is smaller than root's key
    return search(root.left, key)
 
# Driver Code
if __name__ == '__main__':
    root = None
    root = insert(root, 50)
    insert(root, 30)
    insert(root, 20)
    insert(root, 40)
    insert(root, 70)
    insert(root, 60)
    insert(root, 80)
 
    # Key to be found
    key = 6
 
    # Searching in a BST
    if search(root, key) is None:
        print(key, "not found")
    else:
        print(key, "found")
 
    key = 60
 
    # Searching in a BST
    if search(root, key) is None:
        print(key, "not found")
    else:
        print(key, "found")

C#

// C# function to search a given key in a given BST
 
using System;
 
public class Node {
    public int key;
    public Node left, right;
}
 
public class BinaryTree {
    // A utility function to create a new BST node
    public Node NewNode(int item)
    {
        Node temp = new Node();
        temp.key = item;
        temp.left = temp.right = null;
        return temp;
    }
 
    // A utility function to insert
    // a new node with given key in BST
    public Node Insert(Node node, int key)
    {
        // If the tree is empty, return a new node
        if (node == null)
            return NewNode(key);
 
        // Otherwise, recur down the tree
        if (key < node.key)
            node.left = Insert(node.left, key);
        else if (key > node.key)
            node.right = Insert(node.right, key);
 
        // Return the (unchanged) node pointer
        return node;
    }
 
    // Utility function to search a key in a BST
    public Node Search(Node root, int key)
    {
        // Base Cases: root is null or key is present at root
        if (root == null || root.key == key)
            return root;
 
        // Key is greater than root's key
        if (root.key < key)
            return Search(root.right, key);
 
        // Key is smaller than root's key
        return Search(root.left, key);
    }
 
    // Driver Code
    public static void Main()
    {
        Node root = null;
        BinaryTree bt = new BinaryTree();
        root = bt.Insert(root, 50);
        bt.Insert(root, 30);
        bt.Insert(root, 20);
        bt.Insert(root, 40);
        bt.Insert(root, 70);
        bt.Insert(root, 60);
        bt.Insert(root, 80);
 
        // Key to be found
        int key = 6;
 
        // Searching in a BST
        if (bt.Search(root, key) == null)
            Console.WriteLine(key + " not found");
        else
            Console.WriteLine(key + " found");
 
        key = 60;
 
        // Searching in a BST
        if (bt.Search(root, key) == null)
            Console.WriteLine(key + " not found");
        else
            Console.WriteLine(key + " found");
    }
}

Javascript

// Javascript function to search a given key in a given BST
 
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
 
// A utility function to insert
// a new node with given key in BST
function insert(node, key) {
  // If the tree is empty, return a new node
  if (node === null) {
    return new Node(key);
  }
 
  // Otherwise, recur down the tree
  if (key < node.key) {
    node.left = insert(node.left, key);
  } else if (key > node.key) {
    node.right = insert(node.right, key);
  }
 
  // Return the (unchanged) node pointer
  return node;
}
 
// Utility function to search a key in a BST
function search(root, key) {
  // Base Cases: root is null or key is present at root
  if (root === null || root.key === key) {
    return root;
  }
 
  // Key is greater than root's key
  if (root.key < key) {
    return search(root.right, key);
  }
 
  // Key is smaller than root's key
  return search(root.left, key);
}
 
// Driver Code
let root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
 
// Key to be found
let key = 6;
 
// Searching in a BST
if (search(root, key) === null) {
  console.log(key + " not found");
} else {
  console.log(key + " found");
}
 
key = 60;
 
// Searching in a BST
if (search(root, key) === null) {
  console.log(key + " not found");
} else {
  console.log(key + " found");
}

Output

6 not found
60 found

Time complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(h), where h is the height of the BST. This is because the maximum amount of space needed to store the recursion stack would be h.

Related Links:

GeeksforGeeks

Improve

Insertion in Binary Search Tree (BST)

Deletion in Binary Search Tree (BST)

Easy problems on Binary Search Tree

Intermediate problems on Binary Search Tree

Hard problems on Binary Search Tree