Why BST Over Plain Binary Tree in DSA Typescript - Performance Analysis

Time Complexity: Why BST Over Plain Binary Tree

O(n) for plain tree, O(log n) for balanced BST

Understanding Time Complexity

We want to understand why using a Binary Search Tree (BST) is faster than a plain binary tree for searching data.

How does the structure affect the time it takes to find a value?

Scenario Under Consideration

Analyze the time complexity of searching a value in these two tree types.

// Plain binary tree search (no order)
function searchPlainTree(node: TreeNode | null, target: number): boolean {
  if (!node) return false;
  if (node.value === target) return true;
  return searchPlainTree(node.left, target) || searchPlainTree(node.right, target);
}

// BST search (ordered)
function searchBST(node: TreeNode | null, target: number): boolean {
  if (!node) return false;
  if (node.value === target) return true;
  if (target < node.value) return searchBST(node.left, target);
  else return searchBST(node.right, target);
}
    

The first searches all nodes without order; the second uses order to skip parts.

Identify Repeating Operations

Look at what repeats when searching.

• Primary operation: Checking nodes one by one.
• How many times: Plain tree may check every node; BST checks nodes along one path.

How Execution Grows With Input

As the tree grows, how many nodes do we check?

Input Size (n)	Approx. Operations Plain Tree	Approx. Operations BST
10	Up to 10 checks	About 4 checks (height ~ log2 10)
100	Up to 100 checks	About 7 checks (height ~ log2 100)
1000	Up to 1000 checks	About 10 checks (height ~ log2 1000)

Pattern observation: Plain tree search grows linearly with nodes; BST search grows slowly with tree height.

Final Time Complexity

Time Complexity: O(n) for plain tree, O(log n) for balanced BST

BST lets us find values much faster by skipping large parts of the tree.

Common Mistake

[X] Wrong: "BST search always checks half the nodes like binary search on arrays."

[OK] Correct: BST speed depends on tree shape; if unbalanced, it can be as slow as plain tree.

Interview Connect

Knowing why BSTs are faster helps you explain data structure choices clearly and shows you understand how structure affects speed.

Self-Check

What if the BST becomes unbalanced and looks like a linked list? How would the time complexity change?