Why BST Over Plain Binary Tree in DSA C# - Why It Works

Concept Flow - Why BST Over Plain Binary Tree

Start with Tree

↓

Is Tree Binary?

Yes↓

Is Tree Sorted?

↓

Plain Binary

↓

Search: O(n)

↓

Slower

Shows decision from any tree to binary tree, then to BST, highlighting search speed difference.

Execution Sample

DSA C#

class Node {
  public int val;
  public Node left, right;
}

// BST insert and search are faster than plain binary tree search

Defines a node and notes BST operations are faster than plain binary tree search.

Execution Table

Step	Operation	Nodes in Tree	Pointer Changes	Visual State
1	Create root node with value 10	10	root -> Node(10)	10 / . .
2	Insert 5 in plain binary tree (no order)	10, 5	root.left -> Node(5)	10 / 5 .
3	Insert 15 in plain binary tree (no order)	10, 5, 15	root.right -> Node(15)	10 / \ 5 15
4	Search for 15 in plain binary tree (no order)	10, 5, 15	Traverse nodes in any order	Search may check 10 -> 5 -> 15
5	Create BST root node with value 10	10	root -> Node(10)	10 / . .
6	Insert 5 in BST (5 < 10, go left)	10, 5	root.left -> Node(5)	10 / 5 .
7	Insert 15 in BST (15 > 10, go right)	10, 5, 15	root.right -> Node(15)	10 / \ 5 15
8	Search for 15 in BST (compare 10 < 15, go right)	10, 5, 15	Traverse 10 -> 15	Search path: 10 -> 15
9	Search for 5 in BST (compare 10 > 5, go left)	10, 5, 15	Traverse 10 -> 5	Search path: 10 -> 5
10	End of demonstration	10, 5, 15	No changes	BST search faster due to ordered structure

💡 Demonstration ends after showing search paths in both trees

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 7	After Step 8
PlainTreeRoot	null	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
PlainTreeLeft	null	Node(5)	Node(5)	Node(5)	Node(5)	Node(5)	Node(5)
PlainTreeRight	null	null	Node(15)	Node(15)	Node(15)	Node(15)	Node(15)
BSTRoot	null	null	null	Node(10)	Node(10)	Node(10)	Node(10)
BSTLeft	null	null	null	null	Node(5)	Node(5)	Node(5)
BSTRight	null	null	null	null	null	Node(15)	Node(15)

Key Moments - 2 Insights

Why is searching slower in a plain binary tree compared to a BST?

In the execution_table rows 4 and 8, the plain binary tree search checks nodes in no particular order, possibly visiting all nodes, while BST search follows a path guided by value comparisons, reducing steps.

Why do we insert nodes differently in BST than in a plain binary tree?

Rows 2-3 vs 6-7 show that BST inserts nodes based on value comparison (left if smaller, right if larger), keeping the tree ordered, unlike plain binary tree where nodes can be inserted anywhere.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the order of nodes checked during search in the plain binary tree?

A 5 -> 10 -> 15

B 10 -> 15 -> 5

C 10 -> 5 -> 15

D 15 -> 10 -> 5

💡 Hint

Refer to 'Visual State' column at step 4 showing search path

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

A Step 7

B Step 3

C Step 6

D Step 2

💡 Hint

Check 'Operation' column for BST insertions in execution_table

If the plain binary tree was ordered like a BST, how would the search path change at step 4?

A It would check all nodes every time

B It would check fewer nodes by following value comparisons

C It would check nodes in random order

D It would not find the node

💡 Hint

Compare search paths in step 4 (plain) and step 8 (BST) in execution_table

Concept Snapshot

Why BST Over Plain Binary Tree:
- Plain binary tree has no order, search is O(n)
- BST keeps nodes ordered: left < parent < right
- BST search uses comparisons, faster O(log n) average
- Insertions in BST maintain order
- BST is preferred for efficient search and insert

Full Transcript

This visual shows why a Binary Search Tree (BST) is better than a plain binary tree. We start with a tree and check if it is binary and sorted. A plain binary tree has no order, so searching means checking many nodes randomly, which is slow. A BST keeps nodes ordered by value, so searching follows a path left or right based on comparisons, making it faster. The execution table shows inserting nodes 10, 5, and 15 in both trees and searching for nodes. The variable tracker shows how pointers change. Key moments explain why BST search is faster and why insertion differs. The quiz tests understanding of search order and insertion steps. Overall, BST is better for quick search and insert because of its ordered structure.

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 difference

   A plain Binary Tree has no order among nodes, while a BST keeps nodes sorted so left child is smaller and right child is larger.

2. Step 2: Analyze search efficiency

   Because of this order, BST allows searching by comparing and moving left or right, reducing search time to O(log n) on average, unlike 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:

   BST sorted order = faster search [OK]

Hint: BST keeps data sorted for quick searching [OK]

Common Mistakes:

• Thinking BST uses less memory
• Confusing BST with trees having multiple children
• Assuming BST nodes don't have child pointers

2. Which of the following is the correct syntax to declare a node class for a BST in C#?

easy

A. public class Node { public int data; public Node left, right; }

B. class Node { int data; Node left, right; }

C. public struct Node { int data; Node left, right; }

D. public class Node { int data; Node left; Node right; }

Solution

1. Step 1: Check access modifiers and data types

   For BST node, data and child pointers should be accessible, so public fields are preferred for simplicity.

2. Step 2: Verify syntax correctness

   public class Node { public int data; public Node left, right; } correctly declares a public class with public int data and two child nodes left and right of type Node.

3. Final Answer:

   public class Node { public int data; public Node left, right; } -> Option A

4. Quick Check:

   Public class with public fields = correct BST node [OK]

Hint: Use public class with public fields for BST node [OK]

Common Mistakes:

• Using struct instead of class for nodes
• Missing public keyword for fields
• Declaring multiple lines instead of combined declaration

3. What will be the output of the following C# code that inserts values into a BST and then performs an inorder traversal?

class Node {
  public int data; public Node left, right;
  public Node(int val) { data = val; left = right = null; }
}
class BST {
  public Node root;
  public void Insert(int val) {
    root = InsertRec(root, val);
  }
  private Node InsertRec(Node root, int val) {
    if (root == null) return new Node(val);
    if (val < root.data) root.left = InsertRec(root.left, val);
    else root.right = InsertRec(root.right, val);
    return root;
  }
  public void Inorder(Node root) {
    if (root != null) {
      Inorder(root.left);
      Console.Write(root.data + " ");
      Inorder(root.right);
    }
  }
}

var tree = new BST();
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);
tree.Inorder(tree.root);

medium

A. 10 5 15

B. 5 10 15

C. 15 10 5

D. 5 15 10

Solution

1. Step 1: Insert nodes into BST

   Insert 10 as root, then 5 goes to left of 10, 15 goes to right of 10.

2. Step 2: Perform inorder traversal

   Inorder visits left subtree, root, then right subtree. So output is 5 (left), 10 (root), 15 (right).

3. Final Answer:

   5 10 15 -> Option B

4. Quick Check:

   Inorder traversal of BST = sorted order [OK]

Hint: Inorder traversal of BST prints sorted values [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Inserting nodes incorrectly
• Printing nodes in wrong order

4. The following code attempts to insert nodes into a BST but has a bug. What is the bug?

class Node {
  public int data; public Node left, right;
  public Node(int val) { data = val; }
}
class BST {
  public Node root;
  public void Insert(int val) {
    root = InsertRec(root, val);
  }
  private Node InsertRec(Node root, int val) {
    if (root == null) return new Node(val);
    if (val < root.data) root.left = InsertRec(root.left, val);
    else root.right = InsertRec(root.right, val);
    return root;
  }
}

medium

A. root is not initialized before insertion

B. InsertRec method has wrong return type

C. Node constructor does not initialize left and right pointers

D. Missing public keyword for Insert method

Solution

1. Step 1: Check Node constructor

   The constructor sets data but does not initialize left and right pointers to null.

2. Step 2: Verify standard practice for trees

   Node constructors in tree implementations must explicitly set left = right = null; for proper initialization and to avoid potential issues.

3. Final Answer:

   Node constructor does not initialize left and right pointers -> Option C

4. Quick Check:

   Uninitialized child pointers cause runtime errors [OK]

Hint: Always initialize child pointers in node constructor [OK]

Common Mistakes:

• Assuming null pointers cause compile errors
• Ignoring default null initialization in C#
• Confusing method return types

5. You want to store a large collection of unique numbers and perform frequent searches. Why would using a BST be better than a plain Binary Tree, and what is the worst-case time complexity difference?

hard

A. BST nodes have more children, reducing tree height; plain Binary Tree nodes have only two children

B. BST uses less memory, so search is faster; plain Binary Tree uses more memory

C. BST allows duplicate values for faster search; plain Binary Tree does not

D. BST keeps data sorted, allowing average O(log n) search; plain Binary Tree search is O(n)

Solution

1. Step 1: Understand BST advantages

   BST keeps nodes sorted, so searching can skip half the tree at each step, giving average O(log n) time.

2. Step 2: Compare with plain Binary Tree

   Plain Binary Tree has no order, so search may check all nodes, resulting in O(n) time in worst case.

3. Final Answer:

   BST keeps data sorted, allowing average O(log n) search; plain Binary Tree search is O(n) -> Option D

4. Quick Check:

   BST sorted = O(log n) search, plain tree = O(n) [OK]

Hint: BST sorted structure gives faster search than plain tree [OK]

Common Mistakes:

• Thinking BST uses less memory
• Believing BST allows duplicates for speed
• Confusing number of children per node