BST Search Operation in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of searching for 15 in this BST?

Consider the following Binary Search Tree (BST) and the search operation for the value 15.

What will be the output of the search method?

DSA C#

class Node {
    public int Value;
    public Node Left, Right;
    public Node(int val) { Value = val; Left = Right = null; }
}

class BST {
    public Node Root;
    public BST() { Root = null; }

    public bool Search(int val) {
        Node current = Root;
        while (current != null) {
            if (val == current.Value) return true;
            else if (val < current.Value) current = current.Left;
            else current = current.Right;
        }
        return false;
    }
}

// Tree structure:
//       20
//      /  \
//    10    30
//      \     \
//      15    40

BST tree = new BST();
tree.Root = new Node(20);
tree.Root.Left = new Node(10);
tree.Root.Right = new Node(30);
tree.Root.Left.Right = new Node(15);
tree.Root.Right.Right = new Node(40);

bool result = tree.Search(15);
System.Console.WriteLine(result);

A false

B Runtime error

C null

D true

💡 Hint

Remember, the search moves left if the value is smaller, right if larger, and returns true if found.

The value 15 exists in the BST as the right child of 10. The search will find it and return true.

❓ Predict Output

intermediate

What is the output of searching for 25 in this BST?

Using the same BST as before, what will be the output of searching for the value 25?

DSA C#

class Node {
    public int Value;
    public Node Left, Right;
    public Node(int val) { Value = val; Left = Right = null; }
}

class BST {
    public Node Root;
    public BST() { Root = null; }

    public bool Search(int val) {
        Node current = Root;
        while (current != null) {
            if (val == current.Value) return true;
            else if (val < current.Value) current = current.Left;
            else current = current.Right;
        }
        return false;
    }
}

// Tree structure:
//       20
//      /  \
//    10    30
//      \     \
//      15    40

BST tree = new BST();
tree.Root = new Node(20);
tree.Root.Left = new Node(10);
tree.Root.Right = new Node(30);
tree.Root.Left.Right = new Node(15);
tree.Root.Right.Right = new Node(40);

bool result = tree.Search(25);
System.Console.WriteLine(result);

A true

B null

C false

D Runtime error

💡 Hint

Check if 25 exists by moving left or right at each node.

The value 25 is not in the BST. The search will reach a null node and return false.

🧠 Conceptual

advanced

Which property must hold true for the BST search to work correctly?

For the search operation in a Binary Search Tree (BST) to work correctly, which property must the tree satisfy?

A All left subtree nodes have values less than the node, and all right subtree nodes have values greater than the node.

B All nodes have either zero or two children.

C The tree is perfectly balanced with equal nodes on left and right.

D All leaf nodes are at the same depth.

💡 Hint

Think about how the search decides to go left or right.

The BST property requires left subtree nodes to be smaller and right subtree nodes to be larger than the current node for search to work efficiently.

🔧 Debug

advanced

What error occurs when searching in this BST code?

Consider this modified search method in a BST. What error will it cause when searching for any value?

DSA C#

public bool Search(int val) {
    Node current = Root;
    while (current != null) {
        if (val == current.Value) return true;
        else if (val < current.Value) current = current.Right;
        else current = current.Left;
    }
    return false;
}

A The search will always return true regardless of the value.

B The search will always return false even if the value exists.

C NullReferenceException at runtime.

D StackOverflowError due to infinite recursion.

💡 Hint

Check the directions the search moves when value is less or greater.

The search moves right when value is less and left when greater, which is opposite of BST property, so it will not find existing values and return false.

🚀 Application

expert

How many nodes are visited when searching for 40 in this BST?

Given the BST below, how many nodes will the search method visit when searching for the value 40?

Count the nodes checked including the root and the found node.

DSA C#

// Tree structure:
//       25
//      /  \
//    15    50
//   /  \   / \
// 10  22 35  70
//         \
//         40

// Search method is standard BST search moving left if val < node, right if val > node.

A 4

B 3

C 5

D 6

💡 Hint

Trace the path from root to 40 step by step.

The search visits nodes 25, then 50, then 35, then 40, totaling 4 nodes.

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