Why BST Over Plain Binary Tree in DSA Typescript - Why It Works

Concept Flow - Why BST Over Plain Binary Tree

Start with Tree

↓

Is it Binary Search Tree?

↓

Search: Go Left or Right

↓

Find target faster

↓

Efficient operations: Insert, Delete, Search

This flow shows how BST organizes nodes to speed up search and other operations compared to a plain binary tree.

Execution Sample

DSA Typescript

class Node {
  constructor(public val: number, public left: Node | null = null, public right: Node | null = null) {}
}

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

This code inserts values into a BST, placing smaller values to the left and larger to the right.

Execution Table

Step	Operation	Nodes in Tree	Pointer Changes	Visual State
1	Insert 10 (root is null)	10	root = new Node(10)	10
2	Insert 5 (5 < 10, go left)	10 -> 5	root.left = new Node(5)	10 / 5 null
3	Insert 15 (15 > 10, go right)	10 -> 5, 15	root.right = new Node(15)	10 / \ 5 15
4	Insert 7 (7 < 10, go left; 7 > 5, go right)	10 -> 5 -> 7, 15	root.left.right = new Node(7)	10 / \ 5 15 \ 7
5	Search 7 (10 -> left 5 -> right 7 found)	No change	No pointer change	10 / \ 5 15 \ 7
6	Search 20 (10 -> right 15 -> right null, not found)	No change	No pointer change	10 / \ 5 15 \ 7
7	Compare with plain binary tree search (must check all nodes)	10, 5, 15, 7	No pointer change	All nodes checked sequentially
8	End	Tree built and searched	No pointer change	BST structure enables faster search

💡 Search ends when target found or reached null pointer

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
root	null	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
root.left	null	null	Node(5)	Node(5)	Node(5)	Node(5)	Node(5)
root.right	null	null	null	Node(15)	Node(15)	Node(15)	Node(15)
root.left.right	null	null	null	null	Node(7)	Node(7)	Node(7)

Key Moments - 3 Insights

Why does BST search go left or right instead of checking all nodes?

Because BST keeps smaller values on the left and larger on the right, so we only follow one path (see steps 5 and 6 in execution_table). This reduces nodes checked.

What happens if the tree is not a BST when searching?

You must check every node because no order is guaranteed (step 7 shows plain binary tree search checking all nodes). This is slower.

Why do we insert smaller values to the left and larger to the right?

This rule keeps the tree ordered, enabling fast search by deciding direction at each node (shown in steps 2, 3, and 4).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, where is the new node with value 7 inserted?

A As the left child of node 5

B As the right child of node 5

C As the left child of node 10

D As the right child of node 15

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 4 in execution_table

At which step does the search for value 7 find the node?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Operation' column in execution_table where search for 7 is done

If the tree was a plain binary tree without BST order, how would the search change?

A It would check only left children

B It would check only right children

C It would check all nodes sequentially

D It would find nodes faster

💡 Hint

Refer to step 7 in execution_table describing plain binary tree search

Concept Snapshot

Binary Search Tree (BST) keeps nodes ordered: smaller values left, larger right.
This order lets search, insert, and delete run faster than in plain binary trees.
BST search follows one path down, not all nodes.
Plain binary trees have no order, so search checks every node.
Use BST for efficient data lookup and updates.

Full Transcript

This lesson shows why a Binary Search Tree (BST) is better than a plain binary tree. BST keeps nodes ordered so smaller values go left and larger go right. This order lets us search faster by choosing left or right at each node instead of checking all nodes. The example code inserts nodes into a BST. The execution table shows step-by-step how nodes are added and how search works. Key moments explain why BST search is faster and how insertion keeps order. The quiz tests understanding of node placement and search steps. Remember, BST structure speeds up operations compared to unordered binary trees.

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