BST Property and Why It Matters in DSA Typescript - Time & Space Complexity

Time Complexity: BST Property and Why It Matters

O(h)

Understanding Time Complexity

We want to understand how the special order in a Binary Search Tree (BST) helps speed up searching and other operations.

How does this order affect the time it takes to find or add items?

Scenario Under Consideration

Analyze the time complexity of searching a value in a BST.

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 looks for a value by moving left or right depending on comparisons, using the BST order.

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 (if balanced)
100	About 7 (if balanced)
1000	About 10 (if balanced)

Pattern observation: In a balanced BST, steps grow slowly (logarithmically) as input grows.

Final Time Complexity

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

This means the 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 sorted list."

[OK] Correct: A BST can find values faster by skipping half the tree at each step if balanced, unlike a list which checks items one by one.

Interview Connect

Knowing how the BST property affects search time helps you explain why data structures matter and how to choose the right one for fast lookups.

Self-Check

"What if the BST becomes a linked list (all nodes only have one child)? How would the time complexity change?"