Searching In Binary Search Tree In Java

March 20, 2026

Searching in Binary Search Tree

Searching in Binary Search Tree in Java is one of the fastest and most important operations in tree based data structures. A Binary Search Tree (BST) allows efficient searching because it maintains a strict ordering:

Left Subtree < Root < Right Subtree

Using this property, we can eliminate half of the tree at each step, making searching much faster than linear structures.

Example of Binary Search Tree

Search key = 40

Steps:

Compare with 50 → go left
Compare with 30 → go right
Found at 40

        50
       /  \
     30    70
    / \    / \
  20  40  60  80

Properties Of Binary Search Tree:

All the node’s in the left subtree are less than the root node.
Similarly , All the node’s in right subtree are greater than the root node.
The left and right subtree each must also be a binary search tree.

These properties provides an ordering so that the operations like searching ,insertion, deletion, finding maximum key , minimum key can be done fast.

Example for Searching in Binary Search Tree

Steps to find a Node in Binary Search Tree

Suppose we want to search 17 in the above example:

Step 1: Compare 17 with the root element which is 15.
Step 2: 17>15 , so Search for a node in right subtree.
Step 3: Compare 17 with 19 . i.e. 17<19 , so search for an element in left subtree.
Step 4: compare 17 with the left child of 19 . i.e. 17==17 , Hence, stop searching and return true.

Preorder Tree Traversal without Recursion

BST: Search a node in Binary Search Tree

Binary search tree in Data Structures (Introduction)

Insertion in a Binary Search Tree

Learn DSA

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Methods for Searching in Binary Search Tree in Java

Searching in Binary Search Tree in Java can be performed in 2 ways:

Method 1: Recursive Approach
Method 2: Iterative Approach

Algorithms for Searching in Binary Search Tree

Recursive Approach

Iterative Approach

Recursive Approach

search(node, key)
1. If node is null
       return false
2. If node.data == key
       return true
3. If key < node.data
       search(node.left, key)
4. Else
       search(node.right, key)

Iterative Approach

1. Set current = root
2. While current is not null:
       a. If key == current.data → return true
       b. If key < current.data → move to left
       c. Else → move to right
3. Return false

Recursive Method for Searching in Binary Search Tree in Java

Run

class Node {
    int data;
    Node left, right;

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

public class BSTSearchRecursive {

    Node root;

    boolean search(Node node, int key) {

        if (node == null)
            return false;

        if (node.data == key)
            return true;

        if (key < node.data)
            return search(node.left, key);
        else
            return search(node.right, key);
    }

    public static void main(String[] args) {

        BSTSearchRecursive tree = new BSTSearchRecursive();

        // Creating BST
        tree.root = new Node(50);
        tree.root.left = new Node(30);
        tree.root.right = new Node(70);
        tree.root.left.left = new Node(20);
        tree.root.left.right = new Node(40);
        tree.root.right.left = new Node(60);
        tree.root.right.right = new Node(80);

        int key = 40;

        if (tree.search(tree.root, key))
            System.out.println("Element found");
        else
            System.out.println("Element not found");
    }
}

Iterative Method for Searching in Binary Search Tree in Java

Run

class Node {
    int data;
    Node left, right;

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

public class BSTSearchIterative {

    Node root;

    boolean search(int key) {

        Node current = root;

        while (current != null) {

            if (key == current.data)
                return true;

            if (key < current.data)
                current = current.left;
            else
                current = current.right;
        }

        return false;
    }

    public static void main(String[] args) {

        BSTSearchIterative tree = new BSTSearchIterative();

        // Creating BST
        tree.root = new Node(50);
        tree.root.left = new Node(30);
        tree.root.right = new Node(70);
        tree.root.left.left = new Node(20);
        tree.root.left.right = new Node(40);
        tree.root.right.left = new Node(60);
        tree.root.right.right = new Node(80);

        int key = 25;

        if (tree.search(key))
            System.out.println("Element found");
        else
            System.out.println("Element not found");
    }
}

Input 1:

Tree: 50, 30, 70, 20, 40, 60, 80
Search: 40

Output:

Element found

Input 2:

Search: 25

Output:

Element not found

Time Complexity: For Best Case = O(log n)
For Average Case = O(log n)
For Worst Case = O(n)

Space Complexity: For Recursive Method = O(h)
For Iterative Method = O(1)

Frequently Asked Questions

1. What is searching in a Binary Search Tree in Java?

Answer:

It is the process of finding a value using BST properties (left < root < right).

2. What is the time complexity of BST search?

Answer:

Average is O(log n), worst case is O(n).

3. Which is better: recursive or iterative search?

Answer:

Iterative is more space efficient, while recursive is easier to implement.

4. Why is BST search efficient?

Answer:

BST is efficient because it eliminates half of the tree at each step.

5. What is skewed BST?

Answer:

In Skewed BST tree behaves like a linked list, and search becomes O(n).

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Unlock this article for Free,
by logging in

Searching In Binary Search Tree In Java