Searching in BST in Data Structures Theory - Time & Space Complexity

Time Complexity: Searching in BST

O(h)

Understanding Time Complexity

When searching for a value in a Binary Search Tree (BST), we want to know how the time to find that value changes as the tree grows.

We ask: How many steps does it take to find a value when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchBST(node, target) {
  if (node == null) return false;
  if (node.value == target) return true;
  if (target < node.value) {
    return searchBST(node.left, target);
  } else {
    return searchBST(node.right, target);
  }
}
    

This code searches for a target value by moving left or right depending on comparisons, stopping when it finds the value or reaches a leaf.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call moving down one level in 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 of the tree, so the number of steps depends on the tree's height.

Input Size (n)	Approx. Operations (steps)
10	About 3 to 4 steps
100	About 6 to 7 steps
1000	About 9 to 10 steps

Pattern observation: The steps grow slowly, roughly proportional to the tree height, which is often much smaller than the total number of nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time to search depends on the height of the tree, not directly on the total number of nodes.

Common Mistake

[X] Wrong: "Searching a BST always takes time proportional to the number of nodes, O(n)."

[OK] Correct: Because BST search moves down one path, it only visits nodes along that path, which is at most the tree height, not all nodes.

Interview Connect

Understanding how BST search time depends on tree height helps you explain why balanced trees are important and shows you can analyze data structures beyond simple arrays.

Self-Check

"What if the BST is perfectly balanced versus completely skewed? How would the time complexity change?"