Why BST Over Plain Binary Tree in DSA C# - Quick Recap

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a special type of binary tree where each node's left child contains values less than the node, and the right child contains values greater than the node. This helps in faster searching.

beginner

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

Because BST keeps values in order, it allows skipping half of the tree at each step, making search operations faster than in a plain binary tree where no order is guaranteed.

beginner

What is the main disadvantage of a plain binary tree compared to a BST?

A plain binary tree does not maintain any order among nodes, so searching for a value may require checking every node, which is slower.

intermediate

How does the BST property help in insertion?

BST property guides where to insert a new value by comparing it with nodes, placing smaller values to the left and larger to the right, keeping the tree ordered.

beginner

What real-life example can help understand why BST is better than a plain binary tree?

Think of a phone book sorted by names (BST) versus a pile of unsorted papers (plain binary tree). Finding a name in the sorted book is much faster.

What does BST stand for?

A Basic Search Tree

B Binary Search Tree

C Binary Sorted Tree

D Balanced Search Tree

BST stands for Binary Search Tree, a tree with ordered nodes for efficient searching.

In a BST, where are smaller values stored relative to a node?

A Left child

B Right child

C Parent node

D Anywhere

Smaller values are stored in the left child of a node in a BST.

Why is searching in a plain binary tree slower than in a BST?

A Because it has more nodes

B Because it is balanced

C Because it is not ordered

D Because it uses recursion

Plain binary trees are not ordered, so searching may require checking every node.

Which operation benefits most from the BST property?

A Insertion

B Deletion

C Searching

D All of the above

Insertion, deletion, and searching all benefit from the BST's ordered structure.

What is a simple analogy to explain BST advantage?

A A sorted phone book

B A random pile of papers

C A messy desk

D A closed book

A sorted phone book helps find names quickly, like a BST helps find values faster.

Explain in your own words why a Binary Search Tree is preferred over a plain binary tree for searching.

Think about how order helps you find things faster.

Describe how the BST property affects insertion and searching operations.

Consider how the tree structure guides where to put or find a value.

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