BST property and invariant in Data Structures Theory - Time & Space Complexity

Time Complexity: BST property and invariant

O(h)

Understanding Time Complexity

We want to understand how the rules of a Binary Search Tree affect how fast we can find or add items.

Specifically, how does the tree's structure influence the work needed as it grows?

Scenario Under Consideration

Analyze the time complexity of searching a value in a Binary Search Tree (BST).

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 looks for a target value by following the BST rule: left child is smaller, right child is bigger.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

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

Input Size (n)	Approx. Operations (levels visited)
10	About 3 to 10 steps depending on tree shape
100	About 7 to 100 steps depending on tree shape
1000	About 10 to 1000 steps depending on tree shape

Pattern observation: If the tree is balanced, steps grow slowly with input size; if unbalanced, steps can grow as large as the number of nodes.

Final Time Complexity

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

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

Common Mistake

[X] Wrong: "Searching a BST always takes the same time as the number of items (O(n))."

[OK] Correct: Because the BST property lets us skip half the tree at each step if balanced, so time depends on height, not total items.

Interview Connect

Understanding how the BST property controls search speed shows you can reason about data structure efficiency, a key skill in coding interviews.

Self-Check

"What if the BST becomes a linked list (completely unbalanced)? How would the time complexity change?"