Why BST Over Plain Binary Tree in DSA C# - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching?

Consider you want to find a number in a tree structure. Why would using a Binary Search Tree (BST) be better than using a plain Binary Tree?

A BST allows storing duplicate values easily, unlike a plain Binary Tree.

B BST uses less memory than a plain Binary Tree because it stores fewer nodes.

C BST keeps elements sorted, allowing faster search by skipping half the tree at each step.

D BST nodes have only one child, making traversal simpler than in a plain Binary Tree.

💡 Hint

Think about how sorting helps in quickly finding an item.

A Binary Search Tree keeps its elements in sorted order. This means when searching, you can decide to go left or right child based on comparison, effectively skipping half the nodes each time. A plain Binary Tree has no order, so you might have to check every node.

❓ Predict Output

intermediate

Output of searching a value in a plain Binary Tree vs BST

Given the following trees, what will be the output when searching for value 7?

Plain Binary Tree (no order): 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 (linked left to right)

BST: Root 4, left child 2, right child 6, left child of 2 is 1, right child of 2 is 3, left child of 6 is 5, right child of 6 is 7

Assume search prints "Found" if value exists, else "Not Found".

DSA C#

class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

// Plain Binary Tree search (traverses all nodes)
bool SearchPlain(Node root, int target) {
    if (root == null) return false;
    if (root.val == target) return true;
    return SearchPlain(root.left, target) || SearchPlain(root.right, target);
}

// BST search (uses ordering)
bool SearchBST(Node root, int target) {
    if (root == null) return false;
    if (root.val == target) return true;
    if (target < root.val) return SearchBST(root.left, target);
    else return SearchBST(root.right, target);
}

// Output?

A Plain Tree: Found, BST: Found

B Plain Tree: Found, BST: Not Found

C Plain Tree: Not Found, BST: Found

D Plain Tree: Not Found, BST: Not Found

💡 Hint

Both trees contain the value 7, but search methods differ.

Both trees contain the value 7. The plain binary tree search checks all nodes and finds 7. The BST search uses ordering and finds 7 by going right from 4, then right from 6.

🔧 Debug

advanced

Why does this plain Binary Tree search take longer than BST search?

Given the following code snippets for searching a value in a plain Binary Tree and a BST, why does the plain Binary Tree search take longer time?

DSA C#

bool SearchPlain(Node root, int target) {
    if (root == null) return false;
    if (root.val == target) return true;
    return SearchPlain(root.left, target) || SearchPlain(root.right, target);
}

bool SearchBST(Node root, int target) {
    if (root == null) return false;
    if (root.val == target) return true;
    if (target < root.val) return SearchBST(root.left, target);
    else return SearchBST(root.right, target);
}

A Plain Binary Tree search uses recursion; BST search uses iteration making it faster.

B Plain Binary Tree search uses more memory causing slowdowns; BST search uses less memory.

C Plain Binary Tree search has a bug causing infinite loops; BST search does not.

D Plain Binary Tree search checks all nodes; BST search skips half nodes using ordering.

💡 Hint

Think about how ordering helps reduce search steps.

The plain Binary Tree search must check every node because there is no order to guide it. The BST search uses the property that left child is smaller and right child is larger, so it can skip half the nodes each step, making it faster.

🚀 Application

advanced

Choosing data structure for fast lookup in a large dataset

You have a large dataset of unique numbers and need to perform many search queries quickly. Which data structure is better and why?

A Use an unsorted array because searching is faster without sorting overhead.

B Use a Binary Search Tree because it keeps data sorted and allows fast search in O(log n) time on average.

C Use a linked list because it allows easy insertion and deletion.

D Use a plain Binary Tree because it is simpler and uses less memory.

💡 Hint

Think about how sorting affects search speed.

A Binary Search Tree keeps data sorted, allowing fast search by comparing values and moving left or right. Plain Binary Trees and linked lists require checking many elements, and unsorted arrays require scanning all elements for search.

❓ Predict Output

expert

Output after inserting values in a BST vs plain Binary Tree

Consider inserting the values [5, 3, 7, 2, 4, 6, 8] into an empty tree. What is the printed in-order traversal (left-root-right) of the tree after insertion for each type?

DSA C#

// Plain Binary Tree insertion: insert as left child if empty, else right child
// BST insertion: insert maintaining BST property

// In-order traversal prints nodes in sorted order for BST

A Plain Binary Tree in-order: 5 -> 3 -> 7 -> 2 -> 4 -> 6 -> 8; BST in-order: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

B Plain Binary Tree in-order: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8; BST in-order: 5 -> 3 -> 7 -> 2 -> 4 -> 6 -> 8

C Plain Binary Tree in-order: 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2; BST in-order: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

D Plain Binary Tree in-order: 5 -> 7 -> 3 -> 4 -> 2 -> 8 -> 6; BST in-order: 5 -> 3 -> 7 -> 2 -> 4 -> 6 -> 8

💡 Hint

Remember in-order traversal of BST prints sorted values.

In a plain Binary Tree, insertion order determines structure, so in-order traversal prints nodes in insertion order. In a BST, in-order traversal always prints nodes sorted from smallest to largest.

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