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

What is difference between Binary Tree and Binary Search Tree

A binary tree does not impose any ordering rules for node values, while a binary search tree requires strict ordering for the left and right children. and binary search tree ensures that the tree structure allows for efficient searching, insertion, and deletion of nodes, while a binary tree does not have these constraints.

Code Flow for Search In Binary Tree

• Check if the current node is null:

  • If the node (root) is null, return false.

  • This indicates that either the tree is empty or we've reached a leaf node without finding the searchKey.

• Check if the current node contains the searchKey:

  • If root.data is equal to searchKey, print "searchKey found".

  • Return true, indicating the search was successful.

• Search in the right subtree:

  • If the key isn't found in the current node, recursively search the right subtree by calling search(root.right, searchKey).

  • If the key is found in the right subtree, return true.

• Search in the left subtree (if not found in the right subtree):

  • If the key isn't found in the right subtree, recursively search the left subtree by calling search(root.left, searchKey).

  • Return the result of the left subtree search.

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 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;
        }

        /*  continue search in the right subtree.  */
        if (search(root.right, searchKey)) {
            return true;
        }

        /*  continue search in the left subtree. */
        return search(root.left, searchKey);
    }

    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);
        assertFalse(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

• Worst case: O(n)

• Best case: O(1)

• Average case: O(n)

Space Complexity

• O(h) (where h is the height of the tree, and in the worst case, it could be O(n) if the tree is unbalanced.