BST Property and Why It Matters in DSA C++ - 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.

// Check if a value exists in a BST
bool searchBST(TreeNode* root, int val) {
  if (!root) return false;
  if (root->val == val) return true;
  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 following the BST property to decide which side to search next.

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 down tree)
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 number of nodes.

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 items 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 unbalanced (like a linked list), the height can be as big as the number of nodes, making search slow.

Interview Connect

Knowing how the BST property affects search speed helps you explain why balanced trees matter and shows you understand efficient data access.

Self-Check

"What if we changed the BST to a balanced tree like an AVL tree? How would the time complexity change?"