Search In Binary Search Tree

Given a Binary Search Tree and a key, your task is to Search In Binary Search Tree and check whether the given key exists in the tree or not.

Code Flow for Search In Binary Search Tree

Null Check:

• if (null == temp):

  • This condition checks if temp is null, meaning the tree is empty, or we've reached a leaf node without finding the searchKey.

  • If temp is null, the method does nothing (this is a no-op), and the search continues to the next condition.

  • The function will return false after checking all possible paths (because there's a return false at the end of the method).

Search in the Right Subtree:

• else if (searchKey > temp.data):

  • If the searchKey is greater than the value stored in the current node (temp.data), then the search must continue in the right subtree.

  • The method makes a recursive call to search the right child of the current node: search(temp.right, searchKey).

  • The result of this recursive call is returned directly, ensuring the result (true or false) propagate correctly.

Search in the Left Subtree:

• else if (searchKey < temp.data):

  • If the searchKey is less than the value in the current node (temp.data), then the search must continue in the left subtree.

  • The method makes a recursive call to search the left child of the current node: search(temp.left, searchKey).

  • As with the right subtree, the result of this recursive call is returned to ensure the search result propagates.

Key Found:

• else if (searchKey == temp.data):

  • If the searchKey is equal to the value in the current node (temp.data), the key has been found.

  • The method returns true, indicating that the search was successful.

Final Return Statement:

• return false;:

  • This is the fallback return value.

  • If none of the conditions in the if-else chain are met (i.e., the key was not found in the tree), this statement is executed, returning false to indicate that the key does not exist in the tree.

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

import java.util.Objects;

public class BinarySearchTree {
    Node root;

    boolean search(Node root, int searchKey) {
        /*  if root is null, meaning the tree is empty, or a leaf node is reached without finding the searchKey. */
        if (Objects.isNull(root)) {
            return false;
        }
        /*  If the searchKey is greater than the value stored in the current node (temp.data), then the search must continue in the right subtree.  */
        else if (searchKey > root.data) {
            return search(root.right, searchKey);
        }
        /*  If the searchKey is less than the value in the current node (temp.data), then the search must continue in the left subtree. */
        else if (searchKey < root.data) {
            return search(root.left, searchKey);
        }
        /*  If the searchKey is equal to the value in the current node (temp.data), the key has been found. */
        else if (searchKey == root.data) {
            System.out.println(searchKey + " found");
            return true;
        }
        return false;
    }

    void insert(int data) {
        System.out.println("BinarySearchTree.insert data = " + data);
        root = insert(root, data);
    }

    Node insert(Node root, int data) {
        if (Objects.isNull(root)) {
            Node tempNode = new Node(data);
            return tempNode;
        }
        if (data > root.data) {
            root.right = insert(root.right, data);
        } else {
            root.left = insert(root.left, data);
        }
        return root;
    }
}

@Data
class Node {
    int data;
    Node left, right;

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

package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

public class BinarySearchTreeTest {
    @Test
    void testEmptyTree() {
        // Test for an empty tree (null root)
        BinarySearchTree tree = new BinarySearchTree();
        assertFalse(tree.search(null, 1), "Searching for a non-existent key in a single node tree should return false.");
    }

    @Test
    void testSingleNodeTree() {
        // Test for a tree with a single node
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        assertTrue(tree.search(tree.root, 10), "Searching for the only node in a single node tree should return true.");
    }

    @Test
    void testBalancedBinaryTree() {
        // Test for a balanced binary tree
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(2);
        tree.insert(7);
        tree.insert(12);
        tree.insert(18);
        assertTrue(tree.search(tree.root, 12), "Searching for a key should return true.");
    }

    @Test
    void testUnbalancedBinaryTree() {
        // Test for an unbalanced binary tree (sorted order insertion creating a right-skewed tree)
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        assertTrue(tree.search(tree.root, 50), "Searching for a key at a leaf node should return true.");
    }

    @Test
    void testTreeWithNegativeValues() {
        // Test for a tree with negative values
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(-5);
        tree.insert(-3);
        tree.insert(-2);
        tree.insert(-1);
        tree.insert(-7);
        tree.insert(-4);
        assertTrue(tree.search(tree.root, 1), "Searching for a key that is not in the tree should return false.");
    }

    @Test
    void testLargeTree() {
        // Test for a large tree with many nodes
        BinarySearchTree tree = new BinarySearchTree();
        for (int i = 1; i <= 1000; i++) {
            tree.insert(i);
        }
        assertTrue(tree.search(tree.root, 1000), "Searching for a key present in large tree should return true.");
    }
}

plugins {
    id("java")
    id("io.freefair.lombok") version "8.13"
}

group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"

repositories {
    mavenCentral()
}

dependencies {
    testImplementation(platform("org.junit:junit-bom:5.10.0"))
    testImplementation("org.junit.jupiter:junit-jupiter")
}

tasks.test {
    useJUnitPlatform()
}

Complexity Analysis

Time Complexity

• Time Complexity: O(n) (in the worst case)

Space Complexity

• Space Complexity: O(h), where h is the height of the tree. It can be O(log n) for a balanced tree and O(n) for an unbalanced tree.