Searching in Binary Search Tree With Full Explanation

Data Structure / By Rakesh Saini / July 15, 2023

In this tutorial we will learn how to do Searching operation in Node in Binary Search Tree. Please see the full details below for learn about this.

A Binary Search Tree (BST) is a type of binary tree data structure that follows a specific ordering principle. It provides an efficient way to store and retrieve data, particularly when searching for elements.

In a BST, each node contains a key or value, and the structure of the tree ensures that the keys are stored in a specific order. The left child of a node holds a key that is smaller than its parent, while the right child holds a key that is larger. This property enables efficient search, insertion, and deletion operations.

Searching in Binary Search Tree Example Java

To find a value in a Binary Search Tree (BST), you can follow these steps recursively:

Start at the root of the BST.
If the root is null, return false, as the value does not exist in the BST.
If the value you are searching for is equal to the value at the current node, return true.
If the value you are searching for is less than the value at the current node, recursively search in the left subtree.
If the value you are searching for is greater than the value at the current node, recursively search in the right subtree.


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        val = value;
        left = null;
        right = null;
    }
}

class BST {
    TreeNode root;

    public BST() {
        root = null;
    }

    public boolean search(int value) {
        TreeNode current = root;
        while (current != null) {
            if (value == current.val) {
                return true;  // Found the value
            } else if (value < current.val) {
                current = current.left;  // Search in the left subtree
            } else {
                current = current.right;  // Search in the right subtree
            }
        }
        return false;  // Value not found in the BST
    }
}

This code defines the TreeNode class to represent a node in the BST and the BST class that implements the Binary Search Tree data structure. The BST class contains a root node and provides a search method for searching a value in the tree.

The search method performs an iterative search in the BST by traversing the tree from the root until a match is found or the traversal reaches a null node (indicating the value does not exist in the BST).

Calling the Above Code

After creating the above search operation from the main function or from where want to call.


public class Main {
    public static void main(String[] args) {
        BST bst = new BST();
        bst.root = new TreeNode(5);
        bst.root.left = new TreeNode(3);
        bst.root.right = new TreeNode(7);
        bst.root.left.left = new TreeNode(2);
        bst.root.left.right = new TreeNode(4);
        bst.root.right.left = new TreeNode(6);
        bst.root.right.right = new TreeNode(8);

        int valueToSearch = 6;
        boolean found = bst.search(valueToSearch);
        if (found) {
            System.out.println(valueToSearch + " is found in the BST.");
        } else {
            System.out.println(valueToSearch + " is not found in the BST.");
        }
    }
}

Thank you for reaching out this tutorial on FlutterTPoint. You can learn more about the Data Structure Algorithms From Here. The DSA is very important for every developer.