Searching in Binary Search Tree (BST)

Last Updated : 13 Oct, 2025

Given the root of a Binary Search Tree and a value key, find if key is present in the BST or not.

Note: The key may or may not be present in the BST.

Input: key = 7

Output: true
Explanation: 7 is present in the BST.

Input: key = 14

Output: false
Explanation: 14 is not present in the BST.

Try it on GfG Practice

How to search a value in Binary Search Tree:

Let's say we want to search for the number key, 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.
If it's greater we search in the right subtree.
Repeat the above step till no more traversal is possible
If at any iteration, key is found, return True. If the node is null, return False.

Illustration of searching a key in BST:

See the illustration below for a better understanding:

Searching in Binary Search Tree using Recursion:

C++

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int item) {
        data = item;
        left = right = nullptr;
    }
};

bool search(Node* root, int key) {
 
    // root is null -> return false
    if (root == nullptr) return false;

    // if root has key -> return true
    if (root->data == key) return true;

    if (key > root->data) 
        return search(root->right, key);
        
    else
        return search(root->left, key);
}

int main() {
    // Creating BST
    //    6
    //   / \
    //  2   8
    //     / \
    //    7   9
    Node* root = new Node(6);
    root->left = new Node(2);
    root->right = new Node(8);
    root->right->left = new Node(7);
    root->right->right = new Node(9);

    int key = 7;
    
    // Searching for key in BST
    cout << search(root, key) << endl;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create new node
struct Node* newNode(int item) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = item;
    node->left = node->right = NULL;
    return node;
}

bool search(struct Node* root, int key) {
   
    // root is null -> return false
    if (root == NULL) return false;

    // if root has key -> return true
    if (root->data == key) return true;

    if (key > root->data) return search(root->right, key);

    return search(root->left, key);
}

int main() {
    // Creating BST
    //    6
    //   / \
    //  2   8
    //     / \
    //    7   9
    struct Node* root = newNode(6);
    root->left = newNode(2);
    root->right = newNode(8);
    root->right->left = newNode(7);
    root->right->right = newNode(9);

    int key = 7;
    // Searching for key in the BST
    printf("%d\n", search(root, key));
}

Java

// Node Structure
class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class GFG {
    static boolean search(Node root, int key) {
        
        // root is null -> return false
        if( root == null )
            return false;
            
        // if root has key -> return true
        if ( root.data == key)
            return true;

        if (key > root.data)
            return search(root.right, key);

        return search(root.left, key);
    }

    public static void main(String[] args) {
        
        // Creating BST
        //    6
        //   / \
        //  2   8
        //     / \
        //    7   9
        
        Node root = new Node(6);
        root.left = new Node(2);
        root.right = new Node(8);
        root.right.left = new Node(7);
        root.right.right = new Node(9);

        int key = 7;
        // Searching for key in the BST
        System.out.println(search(root, key));
    }
}

Python

# Node structure
class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

def search(root, key):
   
    # root is null -> return false
    if root is None:
        return False

    # if root has key -> return true
    if root.data == key:
        return True

    if key > root.data:
        return search(root.right, key)

    return search(root.left, key)

# Creating BST
#     6
#   / \
#   2   8
#      / \
#     7   9
root = Node(6)
root.left = Node(2)
root.right = Node(8)
root.right.left = Node(7)
root.right.right = Node(9)

key = 7
# Searching for key in the BST
print(search(root, key))

C#

using System;

// Node Structure
class Node {
    public int data;
    public Node left, right;
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class GFG {
    static bool search(Node root, int key) {
       
        // root is null -> return false
        if (root == null) return false;

        // if root has key -> return true
        if (root.data == key) return true;

        if (key > root.data) return search(root.right, key);

        return search(root.left, key);
    }

    public static void Main() {
        // Creating BST
        //    6
        //   / \
        //  2   8
        //     / \
        //    7   9
        Node root = new Node(6);
        root.left = new Node(2);
        root.right = new Node(8);
        root.right.left = new Node(7);
        root.right.right = new Node(9);

        int key = 7;
        // Searching for key in the BST
        Console.WriteLine(search(root, key));
    }
}

JavaScript

// Node structure
class Node {
    constructor(item) {
        this.data = item;
        this.left = null;
        this.right = null;
    }
}

function search(root, key) {
  
    // root is null -> return false
    if (root === null) return false;

    // if root has key -> return true
    if (root.data === key) return true;

    if (key > root.data) return search(root.right, key);

    return search(root.left, key);
}

// Creating BST
//    6
//   / \
//  2   8
//     / \
//    7   9

const root = new Node(6);
root.left = new Node(2);
root.right = new Node(8);
root.right.left = new Node(7);
root.right.right = new Node(9);

const key = 7;

// Searching for key in the BST
console.log(search(root, key));

Output

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

We can avoid the auxiliary space and recursion overhead withe help of iterative implementation. Below is the iterative implementation that works in O(h) time and O(1) auxiliary space.

Searching in Binary Search Tree using Iterative approach:

C++

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int item) {
        data = item;
        left = right = nullptr;
    }
};

bool search(Node* root, int key) {
    bool present = false;
    
    // iterative traversal
    while (root != nullptr) {
        if (root->data == key) {
            present = true;
            break;
        } 
        else if (key > root->data)
            root = root->right;
        else
            root = root->left;
    }
    return present;
}

int main() {
    // Creating BST
    //    6
    //   / \
    //  2   8
    //     / \
    //    7   9
    Node* root = new Node(6);
    root->left = new Node(2);
    root->right = new Node(8);
    root->right->left = new Node(7);
    root->right->right = new Node(9);

    int key = 7;
    
    // Searching for key in BST
    cout << search(root, key) << endl;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create new node
struct Node* newNode(int item) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = item;
    node->left = node->right = NULL;
    return node;
}

bool search(struct Node* root, int key) {
    bool present = false;

    // iterative traversal
    while (root != NULL ) {
        if (root->data == key) {
            present = true;
            break;
        } 
        else if (key > root->data)
            root = root->right;
        else
            root = root->left;
    }
    return present;
}

int main() {
    // Creating BST
    //    6
    //   / \
    //  2   8
    //     / \
    //    7   9
    struct Node* root = newNode(6);
    root->left = newNode(2);
    root->right = newNode(8);
    root->right->left = newNode(7);
    root->right->right = newNode(9);

    int key = 7;
    // Searching for key in the BST
    printf("%d\n", search(root, key));
}

Java

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}
class GFG {
    static boolean search(Node root, int key) {
        boolean present = false;
        
       // iterative traversal
        while( root != null ) {
            if( root.data == key ) {
                present = true;
                break;
            }
            
            else if( key > root.data )
                root = root.right;
            
            else root = root.left;
        }
        return present;
    }

    public static void main(String[] args) {
        
        // Creating BST
        //    6
        //   / \
        //  2   8
        //     / \
        //    7   9
        
        Node root = new Node(6);
        root.left = new Node(2);
        root.right = new Node(8);
        root.right.left = new Node(7);
        root.right.right = new Node(9);

        int key = 7;
        // Searching for key in the BST
        System.out.println(search(root, key));
    }
}

Python

# Node structure
class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

def search(root, key):
    present = False

    # iterative traversal
    while root is not None:
        if root.data == key:
            present = True
            break
        elif key > root.data:
            root = root.right
        else:
            root = root.left

    return present

if __name__ == "__main__":
    # Creating BST
    #     6
    #   / \
    #   2   8
    #      / \
    #     7   9
    root = Node(6)
    root.left = Node(2)
    root.right = Node(8)
    root.right.left = Node(7)
    root.right.right = Node(9)
    
    key = 7
    # Searching for key in the BST
    print(search(root, key))

C#

using System;

class Node {
    public int data;
    public Node left, right;
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class GFG {
    static bool search(Node root, int key) {
        bool present = false;

        // iterative traversal
        while (root != null) {
            if (root.data == key) {
                present = true;
                break;
            } 
            else if (key > root.data)
                root = root.right;
            else
                root = root.left;
        }

        return present;
    }

    public static void Main() {
        // Creating BST
        //    6
        //   / \
        //  2   8
        //     / \
        //    7   9
        Node root = new Node(6);
        root.left = new Node(2);
        root.right = new Node(8);
        root.right.left = new Node(7);
        root.right.right = new Node(9);

        int key = 7;
        // Searching for key in the BST
        Console.WriteLine(search(root, key));
    }
}

JavaScript

// Node structure
class Node {
    constructor(item) {
        this.data = item;
        this.left = null;
        this.right = null;
    }
}

function search(root, key) {
    let present = false;

    // iterative traversal
    while (root !== null) {
        if (root.data === key) {
            present = true;
            break;
        } else if (key > root.data)
            root = root.right;
        else
            root = root.left;
    }

    return present;
}

// Driver code

// Creating BST
//    6
//   / \
//  2   8
//     / \
//    7   9

const root = new Node(6);
root.left = new Node(2);
root.right = new Node(8);
root.right.left = new Node(7);
root.right.right = new Node(9);

const key = 7;

// Searching for key in the BST
console.log(search(root, key));

Output

Time complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(1)

Comment

Article Tags:

Binary Search Tree

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem