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.

// Search for a value in a BST
bool searchBST(Node* root, int target) {
  if (root == nullptr) return false;
  if (root->val == target) return true;
  if (target < root->val) return searchBST(root->left, target);
  else return searchBST(root->right, target);
}
    

This code looks for a target value 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 node at a time.
• How many times: At most once per tree level until the value is found or tree ends.

How Execution Grows With Input

Each step moves down one level in the tree, so the number of steps depends on tree 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: Steps grow slowly as tree size grows, roughly doubling size adds one more step.

Final Time Complexity

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

This means 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 O(n) time because you might check every node."

[OK] Correct: BST search moves down one path only, not all nodes. So it depends on height, not total nodes.

Interview Connect

Understanding BST search time helps you explain efficient data lookup and compare with other structures like arrays or hash tables.

Self-Check

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