BST Search Operation in DSA Python

Mental Model

A binary search tree lets you find a value by comparing and moving left or right, skipping half the tree each time.

Analogy: Like looking for a word in a dictionary by opening near the middle and deciding to go left or right based on alphabetical order.

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

Dry Run Walkthrough

Input: BST: 8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13, search value 7

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

Step 1: Start at root node with value 8

8 [curr]
/ \
3   10
...

Why: We always start searching from the root

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

8 -> [curr->3] -> 10
/ \
1   6
...

Why: 7 is less than 8, so it must be in left subtree if present

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

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

Why: 7 is greater than 3, so search right subtree

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

6 -> [curr->7]

Why: 7 is greater than 6, so move right

Step 5: Compare 7 with 7, found the value

[curr->7]

Why: Value matches current node, search ends successfully

Result:

7 found in BST at node with value 7

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = Node(val)
            return
        curr = self.root
        while True:
            if val < curr.val:
                if curr.left is None:
                    curr.left = Node(val)
                    return
                curr = curr.left
            else:
                if curr.right is None:
                    curr.right = Node(val)
                    return
                curr = curr.right

    def search(self, val):
        curr = self.root
        while curr:
            if val == curr.val:
                return True
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return False

# Driver code
bst = BST()
values = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for v in values:
    bst.insert(v)

search_val = 7
found = bst.search(search_val)
print(f"{search_val} found in BST: {found}")

while curr:

keep searching while current node exists

if val == curr.val:

check if current node value matches search value

elif val < curr.val:

if search value less, go left subtree

else:

if search value greater, go right subtree

Output

7 found in BST: True

Complexity Analysis

Time: O(h) where h is tree height, because search moves down one path from root to leaf

Space: O(1) because search uses only a few pointers, no extra data structures

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

Edge Cases

search in empty BST

search returns False immediately

DSA Python

while curr:

search for value smaller than all nodes

search moves left until None and returns False

DSA Python

curr = curr.left

search for value larger than all nodes

search moves right until None and returns False

DSA Python

curr = curr.right

When to Use This Pattern

When you need to quickly find if a value exists in a sorted tree-like structure, use BST search to skip half the nodes each step.

Common Mistakes

Mistake: Not moving to left or right child correctly based on comparison
Fix: Use if-elif-else to decide direction based on value comparison

Mistake: Forgetting to check if current node is None before accessing its value
Fix: Use while loop condition to ensure current node exists before comparing

Summary

Searches for a value in a binary search tree by moving left or right based on comparisons.

Use when you want fast lookup in a sorted tree structure.

The key is to compare and decide direction at each node, skipping half the tree each step.

Practice

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

easy

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

B. To insert a new value into the BST

C. To delete a value from the BST

D. To traverse all nodes in the BST

Solution

1. Step 1: Understand the purpose of search in BST

   The search operation is used to check if a specific value is present in the BST.

2. Step 2: Differentiate from other operations

   Insertion adds new values, deletion removes values, and traversal visits all nodes. Search only checks for existence.

3. Final Answer:

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

4. Quick Check:

   Search = Find value [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 Python function signature for a BST search method that takes a root node and a key to find?

easy

A. def search(key, root):

B. def search(key):

C. def search(root):

D. def search(root, key):

Solution

1. Step 1: Identify required parameters for BST search

   The search needs the root node to start and the key to find.

2. Step 2: Match parameters order

   Common convention is root first, then key, so def search(root, key): is correct.

3. Final Answer:

   def search(root, key): -> Option D

4. Quick Check:

   Function(root, key) correct signature [OK]

Hint: Root node first, key second in search function [OK]

Common Mistakes:

• Swapping parameter order
• Missing one parameter
• Using only one parameter

3. Given the following BST and the search function call search(root, 15), what will be the output?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    return search(root.right, key)

root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.left = Node(15)
root.right.right = Node(25)

result = search(root, 15)
print(result.val if result else 'Not found')

medium

A. 15

B. 20

C. Not found

D. 10

Solution

1. Step 1: Trace search path for key 15

   Start at root (10). Since 15 > 10, go right to node 20. Then 15 < 20, go left to node 15.

2. Step 2: Check node value

   Node value is 15, matches key, so return this node.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Search found node with value 15 [OK]

Hint: Follow BST rules: left < node < right [OK]

Common Mistakes:

• Stopping search too early
• Going wrong direction at node 20
• Returning root value instead of found node

4. The following code is intended to search for a key in a BST, but it has a bug. What is the error?

def search(root, key):
    if root is None:
        return None
    if root.val == key:
        return root
    if key > root.val:
        return search(root.left, key)
    else:
        return search(root.right, key)

medium

A. The function does not return anything

B. Missing base case for root is None

C. The recursive calls to left and right are swapped

D. The comparison operator should be >= instead of >

Solution

1. Step 1: Analyze recursive calls

   For BST, if key > root.val, search should go right subtree, but code calls search(root.left, key).

2. Step 2: Identify correct direction

   Correct is to go right when key > root.val and left when key < root.val.

3. Final Answer:

   The recursive calls to left and right are swapped -> Option C

4. Quick Check:

   Swap left/right calls to fix search [OK]

Hint: Remember: key > node means go right subtree [OK]

Common Mistakes:

• Swapping left and right recursive calls
• Forgetting base case for None
• Incorrect comparison operators

5. You want to search for the value 8 in the BST below. Which sequence of nodes will the search visit?

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

Choose the correct sequence of visited nodes for search(root, 8).

hard

A. [10, 5, 7]

B. [10, 5, 7, None]

C. [10, 15, 20]

D. [10, 5, 3]

Solution

1. Step 1: Start at root and compare with 8

   8 < 10, go left to 5.

2. Step 2: Compare with 5 and go right

   8 > 5, go right to 7.

3. Step 3: Compare with 7 and go right

   8 > 7, go right which is None (no node), search ends.

4. Final Answer:

   [10, 5, 7, None] -> Option B

5. Quick Check:

   Search path includes None when key not found [OK]

Hint: Follow path until None if key missing [OK]

Common Mistakes:

• Stopping at last node without None
• Going left instead of right at 7
• Ignoring None as end of search