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

Concept Flow - Why BST Over Plain Binary Tree

Start with Plain Binary Tree

↓

Insert nodes anywhere

↓

No order guarantees

↓

Search: Need to check all nodes

↓

Time: O(n) worst case

↓

Switch to Binary Search Tree (BST)

↓

Insert nodes with order: left < root < right

↓

Search: Compare and go left or right

↓

Time: O(log n) average case

↓

More efficient search, insert, delete

Shows how a plain binary tree inserts nodes without order causing slow search, while BST keeps order for faster search.

Execution Sample

DSA Go

type Node struct {
  val int
  left, right *Node
}

// Insert in BST
func insert(root *Node, val int) *Node {
  if root == nil {
    return &Node{val: val}
  }
  if val < root.val {
    root.left = insert(root.left, val)
  } else {
    root.right = insert(root.right, val)
  }
  return root
}

Inserts values into a BST maintaining order for efficient search.

Execution Table

Step	Operation	Nodes in Tree	Pointer Changes	Visual State
1	Insert 10 (Plain Binary Tree)	10	root = new Node(10)	10
2	Insert 5 (Plain Binary Tree)	10, 5	root.left = new Node(5)	10 / 5
3	Insert 15 (Plain Binary Tree)	10, 5, 15	root.right = new Node(15)	10 / \ 5 15
4	Search 15 (Plain Binary Tree)	10, 5, 15	Traverse all nodes	Search checks 10 -> 5 -> 15
5	Insert 10 (BST)	10	root = new Node(10)	10
6	Insert 5 (BST)	10, 5	root.left = insert(root.left, 5)	10 / 5
7	Insert 15 (BST)	10, 5, 15	root.right = insert(root.right, 15)	10 / \ 5 15
8	Search 15 (BST)	10, 5, 15	Compare 15 > 10, go right	Search path: 10 -> 15
9	Search 5 (BST)	10, 5, 15	Compare 5 < 10, go left	Search path: 10 -> 5
10	Search 20 (BST)	10, 5, 15	Compare 20 > 10, go right; 20 > 15, go right (nil)	Search path: 10 -> 15 -> nil (not found)

💡 Search ends when node found or nil reached; BST search faster due to ordered traversal

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 7	After Step 10
root	nil	Node(10)	Node(10)	Node(10)	Node(10)
root.left	nil	Node(5)	Node(5)	Node(5)	Node(5)
root.right	nil	nil	Node(15)	Node(15)	Node(15)
search_path	[]	[]	[]	[]	[10, 15, nil]

Key Moments - 3 Insights

Why does searching in a plain binary tree take longer than in a BST?

Because in a plain binary tree, nodes are inserted without order, so search must check many or all nodes (see execution_table step 4). In BST, search uses order to skip half the tree each step (steps 8-10).

How does BST insertion keep the tree ordered?

BST inserts nodes by comparing values and placing smaller ones to the left and larger to the right (see execution_table steps 6 and 7). This keeps the tree sorted for efficient search.

What happens if the searched value is not in the BST?

Search goes down the tree comparing values until it reaches a nil pointer (no node), meaning value not found (see execution_table step 10).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, how many nodes does the search check in the plain binary tree?

A 1 node

B 3 nodes

C 2 nodes

D 0 nodes

💡 Hint

Check the 'Visual State' column at step 4 showing search path through 10, 5, and 15

At which step does the BST insert the node with value 15?

A Step 6

B Step 3

C Step 7

D Step 2

💡 Hint

Look at the 'Operation' column for BST insertions after step 5

If we insert nodes in random order in a BST, what is the expected search time complexity?

A O(log n)

B O(1)

C O(n)

D O(n log n)

💡 Hint

Refer to the concept_flow showing BST search time as O(log n) average case

Concept Snapshot

Plain Binary Tree inserts nodes anywhere without order.
Search may check all nodes: O(n) time.
BST inserts nodes with order: left < root < right.
Search uses order to skip half tree each step.
BST average search, insert, delete: O(log n) time.
BST is more efficient for search operations.

Full Transcript

A plain binary tree inserts nodes without any order, so searching for a value may require checking many or all nodes, resulting in O(n) time complexity. A binary search tree (BST) inserts nodes by comparing values and placing smaller values to the left and larger to the right, maintaining order. This order allows searching by comparing and moving left or right, skipping half the tree each step, leading to O(log n) average time complexity. The execution table shows how nodes are inserted and searched in both trees, highlighting the efficiency of BST over plain binary tree. Key moments clarify why BST is faster and how insertion maintains order. The visual quiz tests understanding of these steps and concepts.