BST Search Operation in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to compare the current node's value with the target value.

DSA C#

if (node.Value [1] value) return node;

Drag options to blanks, or click blank then click option'

A<

B==

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' or '>' instead of '==' causes wrong comparisons.

Using '!=' will return the node when values are different, which is incorrect.

The search is successful when the current node's value equals the target value.

2fill in blank

medium

Complete the code to decide to search in the left subtree when the target value is smaller.

DSA C#

if (value [1] node.Value) return Search(node.Left, value);

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' will search the wrong subtree.

Using '==' or '!=' here does not help decide the subtree.

If the target value is less than the current node's value, the search continues in the left subtree.

3fill in blank

hard

Fix the error in the recursive call to search the right subtree when the target value is greater.

DSA C#

return Search(node.[1], value);

Drag options to blanks, or click blank then click option'

ALeft

BParent

CRoot

DRight

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'Left' will search the wrong subtree.

Using 'Parent' or 'Root' is not valid for this search step.

When the target value is greater, the search should continue in the right subtree.

4fill in blank

hard

Fill both blanks to complete the base case and recursive search in the BST.

DSA C#

if (node == [1]) return null;
if (value [2] node.Value) return Search(node.Left, value);

Drag options to blanks, or click blank then click option'

Anull

Bnode

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Checking 'node == node' is always true and causes infinite recursion.

Using '>' instead of '<' will search the wrong subtree.

The base case returns null if the node is null (not found). If the value is less than the node's value, search left.

5fill in blank

hard

Fill all three blanks to complete the BST search method with all cases.

DSA C#

if (node == [1]) return null;
if (value [2] node.Value) return Search(node.Left, value);
else if (value [3] node.Value) return Search(node.Right, value);
else return node;

Drag options to blanks, or click blank then click option'

Anull

B<

C>

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' in the recursive conditions instead of in the base case.

Mixing up '<' and '>' operators causing wrong subtree searches.

The method returns null if node is null. It searches left if value is less, right if greater, else returns the node.

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