CSS Prepare

optional · CSS study notes

Binary Search (BST Search)

Context — Distinct From Array Binary Search

  • This topic covers searching within a Binary Search Tree (BST) structure — different from the array-based Binary Search algorithm (see "Binary Search (2017)" page), though the underlying halving logic is conceptually similar

Mechanism

  • Start at the root; compare target with current node:
    • If equal — found
    • If target < node — go to left subtree
    • If target > node — go to right subtree
    • If a null pointer is reached — not found

Pseudocode

BST_SEARCH(node, target):
  IF node == NULL OR node.value == target: RETURN node
  IF target < node.value: RETURN BST_SEARCH(node.left, target)
  ELSE: RETURN BST_SEARCH(node.right, target)

Complexity

  • Time: O(h) where h = tree height — O(log n) if balanced (AVL), but degrades to O(n) if skewed (plain unbalanced BST)
  • Space: O(h) for recursive call stack, O(1) iterative

Why This Matters for the Chapter

  • Directly connects the Binary Search algorithm concept (halving search space) to the Tree data structure — shows why balanced trees (AVL) matter: they guarantee the O(log n) search performance that a plain BST cannot guarantee

Exam Angle / MCQ Trap

Array Binary Search is always O(log n) (array is inherently sorted/indexed); BST search is O(log n) only if the tree is balanced — this conditional guarantee is the key distinction examiners test between the two "Binary Search" concepts.

📌 Sample & Repeated FPSC Questions (2016–2026)

(Only questions genuinely about searching/structuring a Binary Search Tree are included here — not the unrelated array-based Binary Search algorithm, which belongs to the separate "Binary Search (2017)" page.)

📝 Why BST Search Isn't Always O(log n)

2026, Paper I, Q8(c) (8 marks) — A company maintains millions of product IDs and frequently performs searching, insertion, and deletion. Which data structure would be most suitable — Binary Search Tree, AVL Tree, Hash Table, or Array? Justify logically using time complexity and memory considerations.

A plain BST gives average O(log n) search, but with no self-balancing, sequential/near-sorted insertion (common with product IDs generated in batches) can degrade it to a linked-list shape — O(n) worst-case search. An AVL Tree fixes this by guaranteeing O(log n) worst-case search via rotations. A Hash Table beats both with average O(1) search when no sorted/range access is needed — the best answer here, since the scenario has no ordering requirement. Key point for this page: BST search speed is entirely dependent on tree shape/height — that dependency is the crux of nearly every "why balance a BST" exam question.

📝 Self-Balancing BSTs vs Plain BST Search

2025, Paper I, Q6(a) (6 marks) — What are self-balancing Binary Search Trees? Under what circumstances are they preferred over a plain Binary Search Tree?

A self-balancing BST (AVL, Red-Black) automatically rebalances via rotations after every insert/delete, keeping height — and therefore search time — at O(log n). A plain BST offers no such guarantee: its search cost is O(h), and h can range anywhere from O(log n) (balanced) to O(n) (skewed). Self-balancing trees are preferred whenever search performance must stay fast regardless of insertion order (databases, real-time systems); a plain BST is acceptable only when insertion order is known to be random or the tree is built once and rarely modified.

📝 How Insertion Order Determines Search Cost

2018, Paper I, Q5(c) (7 marks) — Random insertion of nodes into a binary search tree would result in what type of tree shape? Elaborate.

Random insertion order gives an expected BST height of O(log n) (≈ 2 ln n), so average search cost stays O(log n) — similar to why randomized quicksort performs well on average. But this is only an average-case result: sorted/near-sorted insertion order produces a fully skewed, linked-list-shaped BST with height O(n), making every search O(n) in the worst case — the exact scenario a balanced tree (AVL) is built to prevent.

📝 Defining "Balanced" for a BST

2018, Paper I, Q6(a) (4 marks) — Define balanced tree both for AVL and Binary Search Tree.

Balanced BST (general sense): a BST is "balanced" if its height is O(log n) relative to n — i.e., left and right subtrees at every node have roughly comparable size, so no root-to-leaf search path is disproportionately long. A plain BST has no enforcement mechanism for this — it depends entirely on insertion order — whereas an AVL tree formally guarantees it via a checkable invariant (balance factor ∈ {-1,0,+1} at every node, restored via rotations whenever violated).

MCQ Trap: "Balanced" is a property a BST may or may not have by chance; AVL is a structure that actively enforces that property after every operation. Search complexity in a BST is always stated as O(h), where h collapses to O(log n) only under the balanced case.