BST Search Operation in DSA Java - Build from Scratch

BST Search Operation

📖 Scenario: Imagine you have a phone book organized as a Binary Search Tree (BST). Each entry has a name and a phone number. You want to find if a particular name exists in the phone book quickly.

🎯 Goal: You will build a simple BST with a few names and phone numbers, then write code to search for a specific name in the BST and print the associated phone number if found, or a message if not found.

📋 What You'll Learn

Create a BST node class with name and phone fields

Manually create a BST with 3 nodes: "Alice", "Bob", and "Charlie"

Create a variable searchName to hold the name to search

Write a method searchBST that searches the BST for searchName

Print the phone number if found or "Name not found" if not

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and many databases use BST or similar tree structures to quickly find information by key.

💼 Career

Understanding BST search is fundamental for software engineers working with data storage, retrieval, and optimization.

1

Create BST nodes with names and phone numbers

Create a class called Node with String name, String phone, Node left, and Node right fields. Then create three Node objects named root, node1, and node2 with these exact values:
root: name = "Bob", phone = "555-1234"
node1: name = "Alice", phone = "555-2345"
node2: name = "Charlie", phone = "555-3456". Connect node1 as left child and node2 as right child of root.

DSA Java

// Define Node class and create root, node1, node2 with given values
// Connect node1 as left child and node2 as right child of root
// Your code here

Hint

Define the Node class with the required fields and constructor. Then create the three nodes with exact names and phone numbers. Connect node1 as left child and node2 as right child of root.

2

Create a variable to hold the search name

Inside the main method, create a String variable called searchName and set it to "Charlie".

DSA Java

class Node {
    String name;
    String phone;
    Node left;
    Node right;

    Node(String name, String phone) {
        this.name = name;
        this.phone = phone;
        this.left = null;
        this.right = null;
    }
}

public class BSTSearch {
    public static void main(String[] args) {
        Node root = new Node("Bob", "555-1234");
        Node node1 = new Node("Alice", "555-2345");
        Node node2 = new Node("Charlie", "555-3456");
        root.left = node1;
        root.right = node2;

        // Create searchName variable and set to "Charlie"
        // Your code here
    }
}

Hint

Inside main, declare String searchName and assign it the value "Charlie".

3

Write the BST search method

Add a static method called searchBST that takes Node root and String searchName as parameters and returns the Node with matching name or null if not found. Use BST search logic comparing searchName with root.name using compareTo. Call searchBST(root, searchName) inside main and store the result in a variable called result.

DSA Java

class Node {
    String name;
    String phone;
    Node left;
    Node right;

    Node(String name, String phone) {
        this.name = name;
        this.phone = phone;
        this.left = null;
        this.right = null;
    }
}

public class BSTSearch {
    public static Node searchBST(Node root, String searchName) {
        // Your code here
    }

    public static void main(String[] args) {
        Node root = new Node("Bob", "555-1234");
        Node node1 = new Node("Alice", "555-2345");
        Node node2 = new Node("Charlie", "555-3456");
        root.left = node1;
        root.right = node2;

        String searchName = "Charlie";

        // Call searchBST and store result
        // Your code here
    }
}

Hint

Write a recursive method that compares searchName with root.name using compareTo. Return the node if found, else search left or right subtree accordingly. Call this method in main and save the result.

4

Print the search result

In the main method, after calling searchBST, print the phone number of the found node using System.out.println(result.phone) if result is not null. Otherwise, print "Name not found".

DSA Java

class Node {
    String name;
    String phone;
    Node left;
    Node right;

    Node(String name, String phone) {
        this.name = name;
        this.phone = phone;
        this.left = null;
        this.right = null;
    }
}

public class BSTSearch {
    public static Node searchBST(Node root, String searchName) {
        if (root == null) {
            return null;
        }
        int cmp = searchName.compareTo(root.name);
        if (cmp == 0) {
            return root;
        } else if (cmp < 0) {
            return searchBST(root.left, searchName);
        } else {
            return searchBST(root.right, searchName);
        }
    }

    public static void main(String[] args) {
        Node root = new Node("Bob", "555-1234");
        Node node1 = new Node("Alice", "555-2345");
        Node node2 = new Node("Charlie", "555-3456");
        root.left = node1;
        root.right = node2;

        String searchName = "Charlie";

        Node result = searchBST(root, searchName);

        // Print phone number if found, else print "Name not found"
        // Your code here
    }
}

Hint

Check if result is not null. If yes, print result.phone. Otherwise, print "Name not found".

Practice

1. What is the main purpose of the search operation in a Binary Search Tree (BST)?

easy

A. To insert a new value into the BST

B. To find whether a given value exists in the BST

C. To delete a value from the BST

D. To traverse all nodes in the BST

Solution

1. Step 1: Understand the search operation

   The search operation checks if a specific value is present in the BST by comparing it with nodes.

2. Step 2: Differentiate from other operations

   Insertion adds new nodes, deletion removes nodes, and traversal visits all nodes. Search only checks presence.

3. Final Answer:

   To find whether a given value exists in the BST -> Option B

4. Quick Check:

   Search = Find value presence [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search returns all nodes
• Assuming search modifies the tree

2. Which of the following is the correct Java method signature for a BST search function that returns a boolean indicating if a value exists?

easy

A. public boolean search(int value)

B. public void search(int value)

C. public int search(int value)

D. public String search(int value)

Solution

1. Step 1: Identify return type for search

   Search should return true or false, so return type must be boolean.

2. Step 2: Check method signature correctness

   Method takes an int value to search and returns boolean. public boolean search(int value) matches this.

3. Final Answer:

   public boolean search(int value) -> Option A

4. Quick Check:

   Return type boolean for search [OK]

Hint: Search returns true/false, so use boolean return type [OK]

Common Mistakes:

• Using void return type for search
• Returning int or String instead of boolean
• Incorrect method parameter types

3. Consider the following BST and the search code snippet:

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

public boolean search(Node root, int key) {
  if (root == null) return false;
  if (root.data == key) return true;
  if (key < root.data) return search(root.left, key);
  else return search(root.right, key);
}

// BST structure:
//       10
//      /  \
//     5    15
//    / \     \
//   3   7     20

What is the output of search(root, 7)?

medium

A. null

B. false

C. true

D. Runtime error

Solution

1. Step 1: Trace search for key 7 starting at root 10

   7 < 10, so search left subtree (node 5).

2. Step 2: Trace search at node 5

   7 > 5, so search right subtree (node 7).

3. Step 3: Trace search at node 7

   Node data equals key (7), so return true.

4. Final Answer:

   true -> Option C

5. Quick Check:

   7 found in BST = true [OK]

Hint: Follow BST rules left/right to find key [OK]

Common Mistakes:

• Stopping search too early
• Confusing left and right subtree directions
• Assuming search returns node instead of boolean

4. The following Java method is intended to search a BST for a key. What is the bug?

public boolean search(Node root, int key) {
  if (root == null) return false;
  if (root.data == key) return true;
  if (key > root.data) return search(root.left, key);
  else return search(root.right, key);
}

medium

A. The recursive calls for left and right subtrees are swapped

B. The base case is missing

C. The method should return int instead of boolean

D. The method does not handle null keys

Solution

1. Step 1: Analyze recursive calls for BST search

   For BST, if key < root.data, search left; if key > root.data, search right.

2. Step 2: Identify swapped calls

   Code calls search(root.left, key) when key > root.data, which is incorrect; left and right calls are swapped.

3. Final Answer:

   The recursive calls for left and right subtrees are swapped -> Option A

4. Quick Check:

   Left/right calls must match key comparison [OK]

Hint: Left subtree for smaller keys, right for larger keys [OK]

Common Mistakes:

• Swapping left and right recursive calls
• Missing base case for null root
• Returning wrong data type

5. Given a BST with nodes inserted in this order: 15, 10, 20, 8, 12, 17, 25. Which sequence of nodes will the search operation visit when searching for 12?

hard

A. 10 -> 15 -> 12

B. 15 -> 20 -> 17 -> 12

C. 15 -> 10 -> 8 -> 12

D. 15 -> 10 -> 12

Solution

1. Step 1: Build BST structure from insertion order

   Insert 15 as root; 10 left of 15; 20 right of 15; 8 left of 10; 12 right of 10; 17 left of 20; 25 right of 20.

2. Step 2: Trace search path for key 12

   Start at 15: 12 < 15, go left to 10; 12 > 10, go right to 12; found key.

3. Final Answer:

   15 -> 10 -> 12 -> Option D

4. Quick Check:

   Search path follows BST rules [OK]

Hint: Follow left if smaller, right if larger until found [OK]

Common Mistakes:

• Visiting nodes not on search path
• Confusing insertion order with search path
• Assuming search visits all nodes