BST Search Operation in DSA C# - Time & Space Complexity

Time Complexity: BST Search Operation

O(h)

Understanding Time Complexity

We want to understand how long it takes to find a value in a Binary Search Tree (BST).

How does the search time change as the tree grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public bool Search(Node root, int target) {
    if (root == null) return false;
    if (root.Value == target) return true;
    if (target < root.Value) return Search(root.Left, target);
    else return Search(root.Right, target);
}
    

This code searches for a target value in a BST by moving left or right depending on comparisons.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down one level of the tree.
• How many times: At most once per tree level until the value is found or a leaf is reached.

How Execution Grows With Input

Each step moves down one level, so the number of steps depends on the tree's height.

Input Size (n)	Approx. Operations (steps)
10	About 4 steps (height ~ log2(10))
100	About 7 steps (height ~ log2(100))
1000	About 10 steps (height ~ log2(1000))

Pattern observation: The steps grow slowly, roughly doubling input size adds only one extra step.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the search time depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Searching a BST always takes the same time as searching an array, so it is O(n)."

[OK] Correct: BST search uses the tree structure to skip half the nodes each step, so it usually takes less time than checking every node.

Interview Connect

Understanding BST search time helps you explain how data structures speed up finding information, a key skill in many coding challenges.

Self-Check

"What if the BST becomes unbalanced and looks like a linked list? How would the time complexity change?"

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