Why BST Over Plain Binary Tree in DSA Typescript - Why This Pattern

Mental Model

A Binary Search Tree (BST) keeps data sorted so finding things is faster than in a plain binary tree.

Analogy: Imagine a phone book where names are sorted alphabetically (BST) versus a random pile of papers (plain binary tree). Searching in the phone book is quicker because you know where to look.

Plain Binary Tree:
    5
   / \
  3   8
 /   / \
1   6   9

Binary Search Tree:
    5
   / \
  3   8
 /   / \
1   6   9

Dry Run Walkthrough

Input: Plain binary tree with nodes 5,3,8,1,6,9; search for 6

Goal: Show how searching for 6 is slower in plain binary tree and faster in BST

Step 1: Start search at root node 5 in plain binary tree

5 [searching] -> left: 3, right: 8

Why: We begin at the root to look for 6

Step 2: Check left child 3, not 6, then check right child 8

5 -> 3 -> 8 [searching]

Why: No order, so we must check both sides

Step 3: Check left child of 8 which is 6, found target

5 -> 3 -> 8 -> 6 [found]

Why: We found 6 but had to check multiple nodes

Step 4: Start search at root node 5 in BST

5 [searching] -> left: 3, right: 8

Why: Start at root in BST

Step 5: Since 6 > 5, move right to 8

5 -> 8 [searching]

Why: BST property tells us to go right for values greater than 5

Step 6: Since 6 < 8, move left to 6 and find target

5 -> 8 -> 6 [found]

Why: BST property guides search directly to 6

Result:

Plain Binary Tree search path: 5 -> 3 -> 8 -> 6
BST search path: 5 -> 8 -> 6
Answer: BST finds 6 faster by skipping unnecessary nodes

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

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

// BST search (uses order to skip branches)
function searchBST(root: TreeNode | null, target: number): boolean {
  if (!root) return false;
  if (root.val === target) return true;
  if (target < root.val) return searchBST(root.left, target); // go left
  else return searchBST(root.right, target); // go right
}

// Build example trees
// Plain binary tree
const rootPlain = new TreeNode(5);
rootPlain.left = new TreeNode(3);
rootPlain.right = new TreeNode(8);
rootPlain.left.left = new TreeNode(1);
rootPlain.right.left = new TreeNode(6);
rootPlain.right.right = new TreeNode(9);

// BST (same structure but obeys BST property)
const rootBST = new TreeNode(5);
rootBST.left = new TreeNode(3);
rootBST.right = new TreeNode(8);
rootBST.left.left = new TreeNode(1);
rootBST.right.left = new TreeNode(6);
rootBST.right.right = new TreeNode(9);

console.log("Plain Binary Tree search for 6:", searchPlain(rootPlain, 6));
console.log("BST search for 6:", searchBST(rootBST, 6));

if (!root) return false;

stop search if node is null

if (root.val === target) return true;

found target node

if (searchPlain(root.left, target)) return true;

search left subtree in plain tree

return searchPlain(root.right, target);

search right subtree if not found left

if (target < root.val) return searchBST(root.left, target);

go left if target less than current node in BST

else return searchBST(root.right, target);

go right if target greater than current node in BST

Output

Plain Binary Tree search for 6: true

BST search for 6: true

Complexity Analysis

Time: O(n) for plain binary tree because we may check every node; O(h) for BST where h is tree height because we skip branches

Space: O(h) for recursion stack in both, where h is tree height

vs Alternative: BST is faster than plain binary tree for search because it uses ordering to avoid checking all nodes

Edge Cases

Empty tree

Search returns false immediately

DSA Typescript

if (!root) return false;

Target not in tree

Search explores necessary nodes and returns false

DSA Typescript

if (!root) return false;

Single node tree with target present

Search finds target immediately

DSA Typescript

if (root.val === target) return true;

When to Use This Pattern

When you need fast search in a tree and the data can be kept sorted, use BST because it lets you skip large parts of the tree.

Common Mistakes

Mistake: Trying to search a BST like a plain binary tree by checking both left and right subtrees
Fix: Use the BST property to decide only one subtree to search based on comparison

Summary

Shows why BST is faster than plain binary tree for searching by using order to skip nodes

Use BST when you want efficient search, insert, and delete in a tree structure

The key insight is BST keeps nodes ordered so you don't waste time checking irrelevant branches