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.