BST vs Hash Map Trade-offs for Ordered Data in DSA C# - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA C#

if (root == null) {
    root = new TreeNode([1]);
}

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

Aroot

Bvalue

Cnull

DnewValue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'root' instead of the value to insert.

Using 'null' which means no value.

We insert the given value as the new root node when the tree is empty.

2fill in blank

medium

Complete the code to check if a key exists in a hash map.

DSA C#

if (hashMap.[1](key)) {
    Console.WriteLine("Key found");
}

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

AAdd

BContainsValue

CContainsKey

DRemove

Attempts:

3 left

💡 Hint

Common Mistakes

Using ContainsValue which checks values, not keys.

Using Add or Remove which modify the map.

The ContainsKey method checks if the key exists in the hash map.

3fill in blank

hard

Fix the error in the BST search method to correctly compare keys.

DSA C#

if (key [1] node.Value) {
    return Search(node.Left, key);
} else if (key [2] node.Value) {
    return Search(node.Right, key);
} else {
    return node;
}

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

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' or '!=' in comparisons instead of '<' or '>'.

In a BST, if the key is less than the node's value, search left; if greater, search right.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that filters keys greater than 10.

DSA C#

var filtered = [1].Where(kv => kv.Key [2] 10).ToDictionary(kv => kv.Key, kv => kv.Value);

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

AhashMap

B>

C<

Dlist

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using a list instead of the hash map.

We filter the hashMap for keys greater than 10 using the '>' operator.

5fill in blank

hard

Fill all three blanks to create a BST in-order traversal that collects values greater than 5.

DSA C#

var result = new List<int>();
void InOrder(TreeNode node) {
    if (node == null) return;
    InOrder(node.[1]);
    if (node.Value [2] 5) {
        result.[3](node.Value);
    }
    InOrder(node.Right);
}

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

ALeft

B>

CAdd

DRight

Attempts:

3 left

💡 Hint

Common Mistakes

Traversing right subtree first instead of left.

Using '<' instead of '>' in comparison.

Using wrong method to add to list.

In-order traversal visits left child first, then current node. We check if value is greater than 5 and add it to the result list.

Practice

1. Which data structure is best suited when you need to maintain data in sorted order and perform fast range queries?

easy

A. Binary Search Tree (BST)

B. Hash Map

C. Stack

D. Queue

Solution

1. Step 1: Understand the need for sorted data

   Maintaining sorted order requires a data structure that keeps elements in order automatically.

2. Step 2: Compare BST and Hash Map for order

   BST keeps elements sorted by design, while Hash Map does not maintain any order.

3. Final Answer:

   Binary Search Tree (BST) -> Option A

4. Quick Check:

   Sorted data needs BST [OK]

Hint: Sorted order needs BST, hash maps don't keep order [OK]

Common Mistakes:

• Thinking hash maps keep data sorted
• Confusing stack or queue with ordered structures
• Assuming hash maps support range queries

2. Which of the following is the correct way to declare a HashMap in C# that maps integers to strings?

easy

A. Hashtable map = new Hashtable();

B. Dictionary map = new Dictionary();

C. Map map = new Map();

D. HashMap map = new HashMap();

Solution

1. Step 1: Identify C# collection for key-value pairs

   C# uses Dictionary for hash map functionality.

2. Step 2: Check syntax correctness

   Dictionary map = new Dictionary(); uses Dictionary with correct syntax; others are invalid or not C# standard.

3. Final Answer:

   Dictionary map = new Dictionary(); -> Option B

4. Quick Check:

   C# hash map = Dictionary [OK]

Hint: Use Dictionary for hash maps in C# [OK]

Common Mistakes:

• Using Java's HashMap syntax in C#
• Trying to use Map or Hashtable with generics incorrectly
• Missing 'new' keyword or wrong constructor

3. Consider the following C# code using a BST and a Dictionary. What will be the output?

var bst = new SortedSet<int>();
bst.Add(10);
bst.Add(5);
bst.Add(15);

var dict = new Dictionary();
dict[10] = "Ten";
dict[5] = "Five";
dict[15] = "Fifteen";

Console.WriteLine(string.Join(",", bst));
Console.WriteLine(string.Join(",", dict.Keys));

medium

A. 5,10,15
10,5,15

B. 5,10,15
5,10,15

C. 10,5,15
5,10,15

D. 10,5,15
10,5,15

Solution

1. Step 1: Understand SortedSet iteration order

   SortedSet stores elements in sorted order, so iterating bst yields 5,10,15.

2. Step 2: Understand Dictionary key order

   Dictionary keys are iterated in insertion order in .NET Core 3.0+, so keys are 10,5,15 inserted in that order.

3. Step 3: Check output

   But the code prints dict.Keys with string.Join, which preserves insertion order: 10,5,15.

4. Final Answer:

   5,10,15 10,5,15 -> Option A

5. Quick Check:

   BST sorted, Dictionary insertion order [OK]

Hint: SortedSet sorts; Dictionary keys keep insertion order [OK]

Common Mistakes:

• Assuming Dictionary keys are sorted
• Confusing SortedSet with HashSet
• Ignoring insertion order of Dictionary keys

4. The following C# code tries to use a Dictionary to get the smallest key quickly. What is the main issue?

var dict = new Dictionary();
dict[20] = "Twenty";
dict[10] = "Ten";
dict[30] = "Thirty";

int minKey = dict.Keys.Min();
Console.WriteLine(minKey);

medium

A. Min() method does not exist for Keys collection

B. Dictionary does not have a Keys property

C. Dictionary.Keys.Min() is inefficient for large data

D. Code will throw a runtime exception

Solution

1. Step 1: Check Dictionary.Keys property

   Dictionary has a Keys property returning a collection of keys.

2. Step 2: Check Min() method usage

   Keys collection supports LINQ Min() to find smallest key, but it requires scanning all keys.

3. Step 3: Identify issue

   Finding min key by scanning all keys is inefficient compared to BST which keeps keys sorted.

4. Final Answer:

   Dictionary.Keys.Min() is inefficient for large data -> Option C

5. Quick Check:

   Min key in Dictionary is slow [OK]

Hint: Dictionary min key needs full scan, slow for big data [OK]

Common Mistakes:

• Thinking Dictionary.Keys.Min() is invalid syntax
• Assuming Dictionary keeps keys sorted
• Expecting constant time min key retrieval

5. You need to store a large dataset of user IDs (integers) with associated names, and you must frequently perform these operations:

• Insert new users
• Find a user by ID quickly
• List users in ascending order of IDs
• Delete users

Which data structure or combination is the best choice in C# to optimize all these operations efficiently?

hard

A. Use List> and sort before each listing

B. Use only Dictionary for all operations

C. Use Dictionary for fast lookup and a separate SortedSet<int> for ordering

D. Use only SortedDictionary for all operations

Solution

1. Step 1: Analyze operation requirements

   Need fast insert, delete, lookup, and ordered listing by user ID.

2. Step 2: Compare data structures

   Dictionary offers fast lookup but no order; SortedDictionary keeps keys sorted and supports fast lookup, insert, delete.

3. Step 3: Evaluate combined approach

   Using Dictionary + SortedSet adds complexity and overhead; SortedDictionary handles all efficiently.

4. Final Answer:

   Use only SortedDictionary<int, string> for all operations -> Option D

5. Quick Check:

   SortedDictionary fits all needs best [OK]

Hint: SortedDictionary keeps keys sorted with fast lookup [OK]

Common Mistakes:

• Using Dictionary alone and sorting keys each time
• Using List and sorting repeatedly, inefficient
• Combining Dictionary and SortedSet unnecessarily