BST Search Operation in DSA Java

Mental Model

A binary search tree lets you find a value by comparing it step-by-step, going left if smaller or right if bigger.

Analogy: Imagine looking for a name in a phone book by opening to the middle, then deciding to look in the left or right half depending on the name's order.

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13

Dry Run Walkthrough

Input: BST with nodes 8,3,10,1,6,14,4,7,13; search for value 7

Goal: Find if value 7 exists in the BST and show the path taken

Step 1: Start at root node 8

8 [curr]
/ \
3   10
/ \    \
1   6    14
   / \   /
  4   7 13

Why: We begin searching from the root of the tree

Step 2: Compare 7 with 8, 7 < 8, move to left child 3

8 -> 3 [curr]
/ \    \
1   6    10
   / \     \
  4   7    14
          /
         13

Why: Since 7 is less than 8, search continues in left subtree

Step 3: Compare 7 with 3, 7 > 3, move to right child 6

8 -> 3 -> 6 [curr]
/ \    \
1   4   7
          
         10
           \
           14
          /
         13

Why: 7 is greater than 3, so go right to find 7

Step 4: Compare 7 with 6, 7 > 6, move to right child 7

8 -> 3 -> 6 -> 7 [curr]
/ \    \
1   4

10
  \
  14
 /
13

Why: 7 is greater than 6, so move right again

Step 5: Compare 7 with 7, found the value

8 -> 3 -> 6 -> 7 [found]
/ \    \
1   4

10
  \
  14
 /
13

Why: Value matches current node, search ends successfully

Result:

8 -> 3 -> 6 -> 7 (value 7 found)

Annotated Code

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) {
        this.val = val;
        left = right = null;
    }
}

public class BSTSearch {
    // Search for a value in BST
    public static boolean search(Node root, int target) {
        if (root == null) return false; // base case: not found
        if (root.val == target) return true; // found the value
        if (target < root.val) {
            return search(root.left, target); // search left subtree
        } else {
            return search(root.right, target); // search right subtree
        }
    }

    // Build example BST
    public static Node buildExampleBST() {
        Node root = new Node(8);
        root.left = new Node(3);
        root.right = new Node(10);
        root.left.left = new Node(1);
        root.left.right = new Node(6);
        root.left.right.left = new Node(4);
        root.left.right.right = new Node(7);
        root.right.right = new Node(14);
        root.right.right.left = new Node(13);
        return root;
    }

    public static void main(String[] args) {
        Node root = buildExampleBST();
        int target = 7;
        boolean found = search(root, target);
        System.out.println("Search for " + target + ": " + (found ? "Found" : "Not Found"));
    }
}

if (root == null) return false; // base case: not found

stop search if reached empty subtree

if (root.val == target) return true; // found the value

check if current node matches target

if (target < root.val) { return search(root.left, target); }

go left if target is smaller

else { return search(root.right, target); }

go right if target is bigger

Output

Search for 7: Found

Complexity Analysis

Time: O(h) where h is tree height because search follows one path down the tree

Space: O(h) due to recursion stack in worst case (skewed tree), O(log n) if balanced

vs Alternative: Compared to linear search in unsorted data O(n), BST search is faster if tree is balanced

Edge Cases

Empty tree

Returns false immediately since root is null

DSA Java

if (root == null) return false; // base case: not found

Value not present in tree

Search reaches null leaf and returns false

DSA Java

if (root == null) return false; // base case: not found

Value is at root

Returns true immediately without recursion

DSA Java

if (root.val == target) return true; // found the value

When to Use This Pattern

When you need to quickly find if a value exists in a sorted tree structure, use BST search to leverage ordering and avoid checking every node.

Common Mistakes

Mistake: Not checking for null root before accessing root.val
Fix: Add base case to return false if root is null before any comparisons

Mistake: Searching both left and right subtrees regardless of value comparison
Fix: Use value comparison to decide only one subtree to search, left or right

Summary

Searches for a value in a binary search tree by comparing and moving left or right.

Use when you want to find if a value exists quickly in a sorted tree.

The key is to use the tree's order to skip half the nodes at each step.

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