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

Practice

1. Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching operations?

easy

A. Because BST keeps elements in sorted order allowing faster search

B. Because BST uses less memory than a plain Binary Tree

C. Because BST nodes can have more than two children

D. Because BST does not require pointers to child nodes

Solution

1. Step 1: Understand the structure of BST vs plain Binary Tree

   A BST stores nodes so that left child is smaller and right child is larger, keeping data sorted. A plain Binary Tree has no order.

2. Step 2: Analyze search efficiency

   Because BST is sorted, searching can skip half the tree at each step, making it faster than searching a plain Binary Tree which may require checking all nodes.

3. Final Answer:

   Because BST keeps elements in sorted order allowing faster search -> Option A

4. Quick Check:

   Sorted structure = faster search [OK]

Hint: BST is sorted, plain tree is not, so search is faster [OK]

Common Mistakes:

• Thinking BST uses less memory
• Confusing number of children in BST
• Assuming BST has no pointers

2. Which of the following is the correct TypeScript syntax to declare a node in a Binary Search Tree?

easy

A. class Node { value: number; left: Node | null; right: Node | null; }

B. function Node(value) { this.value = value; this.left = null; this.right = null; }

C. interface Node { value: string; left: Node; right: Node; }

D. type Node = { value: number; left?: Node; right?: Node }

Solution

1. Step 1: Identify correct TypeScript class syntax for BST node

   class Node { value: number; left: Node | null; right: Node | null; } correctly declares a class with value and nullable left and right nodes using TypeScript types.

2. Step 2: Check other options for correctness

   function Node(value) { this.value = value; this.left = null; this.right = null; } is JavaScript function style, not TypeScript class. interface Node { value: string; left: Node; right: Node; } uses string value and non-nullable children which is incorrect. type Node = { value: number; left?: Node; right?: Node } uses optional children but is a type alias, not a class.

3. Final Answer:

   class Node { value: number; left: Node | null; right: Node | null; } -> Option A

4. Quick Check:

   TypeScript class with nullable children = class Node { value: number; left: Node | null; right: Node | null; } [OK]

Hint: Look for TypeScript class with nullable left/right nodes [OK]

Common Mistakes:

• Confusing JavaScript function with TypeScript class
• Using non-nullable children causing errors
• Using wrong value types

3. Given the following BST insertion code snippet, what will be the in-order traversal output after inserting values 10, 5, 15, 3, 7?

medium

A. [5, 3, 7, 10, 15]

B. [10, 5, 15, 3, 7]

C. [15, 10, 7, 5, 3]

D. [3, 5, 7, 10, 15]

Solution

1. Step 1: Insert values into BST in given order

   Insert 10 as root, 5 to left, 15 to right, 3 to left of 5, 7 to right of 5.

2. Step 2: Perform in-order traversal (left, root, right)

   Traverse left subtree: 3, 5, 7; then root 10; then right subtree 15. Combined: [3, 5, 7, 10, 15]

3. Final Answer:

   [3, 5, 7, 10, 15] -> Option D

4. Quick Check:

   In-order traversal of BST = sorted values [OK]

Hint: In-order traversal of BST always gives sorted list [OK]

Common Mistakes:

• Confusing traversal order
• Inserting nodes incorrectly
• Mixing up left and right children

4. Identify the bug in this BST insertion function snippet in TypeScript:

function insert(root: Node | null, val: number): Node {
  if (!root) return new Node(val);
  if (val < root.value) insert(root.left, val);
  else insert(root.right, val);
  return root;
}

medium

A. Node constructor is called without new keyword

B. Missing return statements for recursive calls

C. Incorrect comparison operator for BST insertion

D. Function does not handle duplicate values

Solution

1. Step 1: Analyze recursive calls in insertion

   The recursive calls insert(root.left, val) and insert(root.right, val) do not assign the returned node back to root.left or root.right.

2. Step 2: Identify missing return assignments

   Without assigning, the tree structure does not update. Correct code should be root.left = insert(root.left, val) and root.right = insert(root.right, val).

3. Final Answer:

   Missing return statements for recursive calls -> Option B

4. Quick Check:

   Recursive insert must update child links [OK]

Hint: Always assign recursive insert results to child nodes [OK]

Common Mistakes:

• Not assigning recursive call results
• Using wrong comparison operators
• Ignoring duplicates silently

5. You have a plain Binary Tree and a BST both containing the same values. Which operation benefits the most from using the BST instead of the plain Binary Tree, and why?

hard

A. Traversing all nodes, because BST traversal is faster than plain tree traversal

B. Inserting a new value, because BST insertion is always O(1)

C. Searching for a value, because BST allows O(log n) average time search

D. Deleting a node, because BST deletion never requires rebalancing

Solution

1. Step 1: Compare searching in BST vs plain Binary Tree

   BST keeps nodes sorted, enabling binary search-like behavior with average O(log n) time. Plain Binary Tree has no order, so search is O(n).

2. Step 2: Evaluate other operations

   Insertion in BST is not always O(1), deletion may require rebalancing, and traversal visits all nodes in both trees equally.

3. Final Answer:

   Searching for a value, because BST allows O(log n) average time search -> Option C

4. Quick Check:

   BST speeds up search, not insertion or traversal [OK]

Hint: BST speeds up search, not insertion or traversal [OK]

Common Mistakes:

• Thinking insertion is always O(1)
• Assuming deletion never needs rebalancing
• Believing traversal is faster in BST