Why BST Over Plain Binary Tree in DSA C# - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a value into a Binary Search Tree (BST).

DSA C#

public class Node {
    public int Value;
    public Node Left, Right;
    public Node(int value) {
        Value = value;
        Left = Right = null;
    }
}

public Node Insert(Node root, int value) {
    if (root == null) {
        return new Node(value);
    }
    if (value [1] root.Value) {
        root.Left = Insert(root.Left, value);
    } else {
        root.Right = Insert(root.Right, value);
    }
    return root;
}

Drag options to blanks, or click blank then click option'

A<

B==

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' causes wrong placement of nodes.

Using '==' in comparison leads to incorrect logic.

In a BST, values less than the current node go to the left subtree, so we use '<' to decide where to insert.

2fill in blank

medium

Complete the code to search for a value in a BST.

DSA C#

public bool Search(Node root, int value) {
    if (root == null) return false;
    if (root.Value == value) return true;
    if (value [1] root.Value) {
        return Search(root.Left, value);
    } else {
        return Search(root.Right, value);
    }
}

Drag options to blanks, or click blank then click option'

A>=

B==

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Searching right subtree when value is smaller.

Using equality operator in wrong place.

To search in BST, if the value is less than current node, search left subtree.

3fill in blank

hard

Fix the error in the code that finds the minimum value node in a BST.

DSA C#

public Node FindMin(Node root) {
    while (root.[1] != null) {
        root = root.Left;
    }
    return root;
}

Drag options to blanks, or click blank then click option'

ALeft

BRight

CRightChild

DLeftChild

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'Right' instead of 'Left' causes wrong minimum.

Using incorrect property names like 'LeftChild'.

The minimum value in BST is found by going left until no more left child exists.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps node values to their depths, but only for nodes with values {{BLANK_1}} 10 and depths {{BLANK_2}} 2.

DSA C#

var depthMap = new Dictionary<int, int>();
foreach (var node in nodes) {
    if (node.Value [1] 10 && node.Depth [2] 2) {
        depthMap[node.Value] = node.Depth;
    }
}

Drag options to blanks, or click blank then click option'

A>

B<

C>=

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' for values.

Using '>' instead of '<=' for depths.

We want values greater than 10 and depths less than or equal to 2.

5fill in blank

hard

Fill all three blanks to create a dictionary that stores uppercase node names as keys, their values as values, but only if value {{BLANK_1}} 50, name {{BLANK_2}} 'A', and depth {{BLANK_3}} 3.

DSA C#

var filteredNodes = new Dictionary<string, int>();
foreach (var node in nodes) {
    if (node.Value [1] 50 && node.Name [2] "A" && node.Depth [3] 3) {
        filteredNodes[node.Name.ToUpper()] = node.Value;
    }
}

Drag options to blanks, or click blank then click option'

A>

B==

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' instead of '>' for value.

Using '!=' instead of '==' for name.

Using '>=' instead of '<' for depth.

We want values greater than 50, names equal to 'A', and depths less than 3.

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