BST Search Operation in DSA Javascript - 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, target) {
  if (root === null) return false;
  if (root.value === target) return true;
  if (target < root.value) {
    return searchBST(root.left, target);
  } else {
    return searchBST(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 each time.
• How many times: At most once per tree level, until the target 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 (tree height)
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly, roughly with the height of the tree, not the total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the search time depends on the tree height, which is the number of levels from root to leaf.

Common Mistake

[X] Wrong: "Searching a BST always takes O(log n) time because it's a tree."

[OK] Correct: If the tree is not balanced, height can be as big as n, making search O(n) in the worst case.

Interview Connect

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

Self-Check

"What if the BST is perfectly balanced? How would the time complexity change compared to a skewed tree?"