BST Search Operation in DSA C# - Build from Scratch

BST Search Operation

📖 Scenario: Imagine you have a phone book organized as a Binary Search Tree (BST). Each entry has a name and a phone number. You want to find if a certain name exists in the phone book quickly.

🎯 Goal: You will build a simple BST with some names and phone numbers, then write code to search for a specific name in the BST and print the phone number if found or a message if not.

📋 What You'll Learn

Create a BST node class with Name, PhoneNumber, Left, and Right properties

Manually build a BST with 5 nodes using the given names and phone numbers

Create a variable searchName with the exact name to search

Write a method SearchBST that searches the BST for searchName

Print the phone number if found or "Name not found" if not

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and many databases use BSTs or similar trees to quickly find information by keys like names.

💼 Career

Understanding BST search is fundamental for software developers working with data structures, databases, and efficient data retrieval.

1

Create BST Node Class and Build Tree

Create a class called BSTNode with public string properties Name and PhoneNumber, and public BSTNode properties Left and Right. Then create a BST with these exact nodes and structure:
root node: Name = "John", PhoneNumber = "555-1234"
Left child of root: Name = "Alice", PhoneNumber = "555-2345"
Right child of root: Name = "Mike", PhoneNumber = "555-3456"
Right child of "Alice": Name = "Bob", PhoneNumber = "555-4567"
Right child of "Mike": Name = "Zara", PhoneNumber = "555-5678"

DSA C#

// Define BSTNode class and create the BST nodes and links
// Your code here

Hint

Start by defining the BSTNode class with the required properties and constructor. Then create the root node and assign its left and right children as described.

2

Create Search Name Variable

Create a string variable called searchName and set it to the exact value "Bob".

DSA C#

public class BSTNode
{
    public string Name { get; set; }
    public string PhoneNumber { get; set; }
    public BSTNode Left { get; set; }
    public BSTNode Right { get; set; }

    public BSTNode(string name, string phoneNumber)
    {
        Name = name;
        PhoneNumber = phoneNumber;
        Left = null;
        Right = null;
    }
}

BSTNode root = new BSTNode("John", "555-1234");
root.Left = new BSTNode("Alice", "555-2345");
root.Right = new BSTNode("Mike", "555-3456");
root.Left.Right = new BSTNode("Bob", "555-4567");
root.Right.Right = new BSTNode("Zara", "555-5678");

// Create searchName variable
// Your code here

Hint

Just create a string variable named searchName and assign it the value "Bob".

3

Write BST Search Method

Write a method called SearchBST that takes a BSTNode called node and a string called name. It should return the BSTNode where Name equals name, or null if not found. Use the BST property to decide to search left or right.

DSA C#

BSTNode SearchBST(BSTNode node, string name)
    if (node == null)
        return null;
    int compare = string.Compare(name, node.Name);
    if (compare == 0)
        return node;
    else if (compare < 0)
        return SearchBST(node.Left, name);
    else
        return SearchBST(node.Right, name);
// Print search result below

Hint

Use recursion. Compare the name with node.Name. If equal, return the node. If name is smaller, search left. Otherwise, search right.

4

Print Search Result

Call SearchBST with root and searchName. If the result is not null, print the found node's phone number using Console.WriteLine. Otherwise, print exactly "Name not found".

DSA C#

Hint

Call SearchBST(root, searchName). If the result is not null, print result.PhoneNumber. Otherwise, print "Name not found".

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