BST Search Operation in DSA Typescript - 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.

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if (root === null || root.val === val) return root;
  if (val < root.val) return searchBST(root.left, val);
  else return searchBST(root.right, val);
}
    

This code searches for a 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 the input size adds only one more 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 a balanced tree."

[OK] Correct: If the tree is not balanced, it can become like a linked list, making search take much longer.

Interview Connect

Understanding BST search time helps you explain how data structure shape affects performance, a key skill in coding interviews.

Self-Check

What if the BST is perfectly balanced? How does that affect the search time complexity?