BST Search Operation in DSA C#

Mental Model

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

Analogy: Like looking for a name in a phone book by opening to the middle and deciding to go left or right depending on the name.

      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 value 7 exists in the BST and show the path taken

Step 1: Start at root node with value 8

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

Why: We always start searching from the root of the BST

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

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

Why: In BST, smaller values are on the left subtree

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

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

Why: In BST, larger values are on the right subtree

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

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

Why: Continue moving right because 7 is greater than 6

Step 5: Compare 7 with 7, found the value

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

Why: Value matches current node, search successful

Result:

8 -> 3 -> 6 -> 7 -> null
Value 7 found in BST

Annotated Code

DSA C#

using System;

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

class BST
{
    public Node root;

    public BST()
    {
        root = null;
    }

    public bool Search(int value)
    {
        Node curr = root;
        while (curr != null)
        {
            if (value == curr.data)
                return true; // found value
            else if (value < curr.data)
                curr = curr.left; // go left
            else
                curr = curr.right; // go right
        }
        return false; // not found
    }

    public void Insert(int value)
    {
        root = InsertRec(root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
            return new Node(value);
        if (value < root.data)
            root.left = InsertRec(root.left, value);
        else if (value > root.data)
            root.right = InsertRec(root.right, value);
        return root;
    }

    public void PrintInOrder(Node node)
    {
        if (node == null) return;
        PrintInOrder(node.left);
        Console.Write(node.data + " -> ");
        PrintInOrder(node.right);
    }
}

class Program
{
    static void Main()
    {
        BST tree = new BST();
        int[] values = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        foreach (int val in values)
            tree.Insert(val);

        tree.PrintInOrder(tree.root);
        Console.WriteLine("null");

        int searchVal = 7;
        bool found = tree.Search(searchVal);
        if (found)
            Console.WriteLine($"Value {searchVal} found in BST");
        else
            Console.WriteLine($"Value {searchVal} not found in BST");
    }
}

Node curr = root;

start search from root node

while (curr != null)

continue until we reach end or find value

if (value == curr.data) return true;

check if current node has the value

else if (value < curr.data) curr = curr.left;

move left if value is smaller

else curr = curr.right;

move right if value is larger

Output

1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14 -> null

Value 7 found in BST

Complexity Analysis

Time: O(h) where h is the height of the tree, because we move down one level each step until we find the value or reach a leaf

Space: O(1) because we only use a pointer to traverse without extra storage

vs Alternative: Compared to searching in an unsorted list which is O(n), BST search is faster if the tree is balanced because it skips half the nodes each step

Edge Cases

Empty tree

Search returns false immediately because root is null

DSA C#

while (curr != null)

Value not present in tree

Search moves down until curr is null and returns false

DSA C#

while (curr != null)

Value is at root

Search finds value immediately and returns true

DSA C#

if (value == curr.data) return true;

When to Use This Pattern

When you need to quickly find if a value exists in a sorted tree structure, use BST search because it efficiently narrows down the search path by comparing values.

Common Mistakes

Mistake: Not moving to left or right child correctly based on comparison
Fix: Use if-else to move left if value is smaller, right if larger

Mistake: Forgetting to check if current node is null before accessing data
Fix: Use while loop condition to ensure curr is not null 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 does the search operation in a Binary Search Tree (BST) do?

easy

A. Traverses all nodes in the BST

B. Deletes a node from the BST

C. Inserts a new node into the BST

D. Finds whether a given value exists in the BST

Solution

1. Step 1: Understand the purpose of BST search

   The search operation checks if a specific value is present in the BST by comparing values starting from the root.

2. Step 2: Differentiate from other operations

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

3. Final Answer:

   Finds whether a given value exists in the BST -> Option D

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insert or delete [OK]

Common Mistakes:

• Confusing search with insertion
• Thinking search deletes nodes
• Assuming search visits all nodes

2. Which of the following is the correct C# syntax to start searching for a value in a BST with root node root and target value key?

easy

A. bool found = root.Search(key);

B. bool found = Search(root, key);

C. bool found = root.search(key);

D. bool found = Search(key, root);

Solution

1. Step 1: Understand typical BST search method signature

   Usually, search is a static or instance method taking the root node and key as parameters, like Search(root, key).

2. Step 2: Analyze options for correct syntax

   bool found = Search(root, key); matches the common pattern. bool found = root.Search(key); assumes Search is an instance method on root, which may not exist. bool found = root.search(key); uses lowercase 'search' which is not standard C# naming. bool found = Search(key, root); has parameters reversed.

3. Final Answer:

   bool found = Search(root, key); -> Option B

4. Quick Check:

   Search(root, key) is standard call [OK]

Hint: Search usually takes root and key as parameters [OK]

Common Mistakes:

• Using lowercase method names in C#
• Reversing parameter order
• Assuming search is a method on node instance

3. Consider the following C# code for searching a BST:

class Node {
  public int val;
  public Node left, right;
  public Node(int v) { val = v; left = right = null; }
}

bool Search(Node root, int key) {
  if (root == null) return false;
  if (root.val == key) return true;
  if (key < root.val) return Search(root.left, key);
  else return Search(root.right, key);
}

// BST structure:
//       10
//      /  \
//     5   15
//    /    / \
//   2    12 20

Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(2);
root.right.left = new Node(12);
root.right.right = new Node(20);

Console.WriteLine(Search(root, 12));
Console.WriteLine(Search(root, 7));

What is the output?

medium

A. True\nFalse

B. False\nTrue

C. True\nTrue

D. False\nFalse

Solution

1. Step 1: Trace Search(root, 12)

   Start at root 10: 12 > 10, go right to 15. 12 < 15, go left to 12. Found 12, return true.

2. Step 2: Trace Search(root, 7)

   Start at root 10: 7 < 10, go left to 5. 7 > 5, go right which is null. Return false.

3. Final Answer:

   True False -> Option A

4. Quick Check:

   12 found = True, 7 not found = False [OK]

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

Common Mistakes:

• Confusing left and right child directions
• Assuming 7 is in the tree
• Not returning false on null node

4. The following C# code attempts to search a BST but has a bug:

bool Search(Node root, int key) {
  if (root == null) return false;
  if (root.val == key) return true;
  if (key > root.val) return Search(root.left, key);
  else return Search(root.right, key);
}

What is the bug in this code?

medium

A. It searches left subtree when key is greater than root value

B. It returns true when root is null

C. It does not check if root value equals key

D. It does not handle duplicate keys

Solution

1. Step 1: Analyze the direction of subtree search

   When key > root.val, the search should go to the right subtree, but code incorrectly goes left.

2. Step 2: Confirm other conditions are correct

   Code correctly returns false if root is null and checks equality properly.

3. Final Answer:

   It searches left subtree when key is greater than root value -> Option A

4. Quick Check:

   Greater key goes right, not left [OK]

Hint: Greater keys go right subtree, smaller go left [OK]

Common Mistakes:

• Swapping left and right subtree in conditions
• Missing null check
• Ignoring equality check

5. You have a BST with nodes inserted in this order: 8, 3, 10, 1, 6, 14, 4, 7, 13. You want to search for the value 7. Which sequence of nodes will the search visit?

hard

A. 8 -> 3 -> 4 -> 7

B. 8 -> 10 -> 14 -> 7

C. 8 -> 3 -> 6 -> 7

D. 8 -> 6 -> 7

Solution

1. Step 1: Build the BST structure mentally

   Insert 8 as root. 3 left of 8. 10 right of 8. 1 left of 3. 6 right of 3. 14 right of 10. 4 left of 6. 7 right of 6. 13 left of 14.

2. Step 2: Trace search for 7

   Start at 8: 7 < 8 go left to 3. 7 > 3 go right to 6. 7 > 6 go right to 7. Found 7.

3. Final Answer:

   8 -> 3 -> 6 -> 7 -> Option C

4. Quick Check:

   Search path follows BST rules [OK]

Hint: Compare key at each node, go left if smaller, right if larger [OK]

Common Mistakes:

• Skipping nodes in path
• Going left when should go right
• Confusing insertion order with search path