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

Time Complexity: BST Property and Why It Matters

O(h)

Understanding Time Complexity

We want to understand how the special rule of a Binary Search Tree (BST) affects how fast we can find or add items.

How does this rule help us work faster as the tree grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchBST(root, val) {
  if (!root) return null;
  if (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 based on the BST rule.

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 tree ends.

How Execution Grows With Input

Each step moves down one level, so the number of steps grows with the tree's height.

Input Size (n)	Approx. Operations
10	About 4 steps (if tree is balanced)
100	About 7 steps
1000	About 10 steps

Pattern observation: Steps grow slowly as tree size grows, if the tree stays balanced.

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 items it has.

Common Mistake

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

[OK] Correct: If the tree is unbalanced, it can act like a list, making search slower. But if balanced, search is faster than checking every item.

Interview Connect

Knowing how the BST rule helps search quickly shows you understand why data structures matter for speed, a key skill in coding interviews.

Self-Check

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