BST vs Hash Map Trade-offs for Ordered Data in DSA Typescript - Build Both Approaches

BST vs Hash Map Trade-offs for Ordered Data

📖 Scenario: Imagine you are managing a small library system. You want to store book titles and their number of copies. You want to quickly find how many copies a book has, but also sometimes list books in alphabetical order.

🎯 Goal: You will create a simple data structure using a JavaScript object (hash map) and a sorted array (to simulate BST behavior) to understand the trade-offs between fast lookup and ordered data.

📋 What You'll Learn

Create a hash map object called bookCopies with given book titles and copies

Create a sorted array called sortedBooks containing the book titles in alphabetical order

Write a function getCopiesFromMap that takes a book title and returns copies from the hash map

Write a function listBooksInOrder that returns the sorted list of book titles

Print the number of copies for a specific book using getCopiesFromMap

Print the list of books in alphabetical order using listBooksInOrder

💡 Why This Matters

🌍 Real World

Libraries, inventory systems, and many apps need to store data for quick lookup and sometimes in order for reports or display.

💼 Career

Understanding these trade-offs helps software developers choose the right data structure for performance and functionality.

1

Create the hash map of books and copies

Create a variable called bookCopies as an object with these exact entries: 'The Hobbit': 5, '1984': 8, 'Brave New World': 3, 'Fahrenheit 451': 6

DSA Typescript

// Create the bookCopies object with the given books and copies
// Your code here

Hint

Use curly braces {} to create an object and add key-value pairs for each book and its copies.

2

Create a sorted array of book titles

Create a variable called sortedBooks as an array containing the book titles from bookCopies sorted alphabetically

DSA Typescript

const bookCopies = {
  'The Hobbit': 5,
  '1984': 8,
  'Brave New World': 3,
  'Fahrenheit 451': 6
};

// Create sortedBooks array with book titles sorted alphabetically
// Your code here

Hint

Use Object.keys(bookCopies) to get the titles, then .sort() to order them alphabetically.

3

Write functions for lookup and ordered listing

Write a function called getCopiesFromMap that takes a parameter title and returns the number of copies from bookCopies. Also write a function called listBooksInOrder that returns the sortedBooks array

DSA Typescript

const bookCopies = {
  'The Hobbit': 5,
  '1984': 8,
  'Brave New World': 3,
  'Fahrenheit 451': 6
};

const sortedBooks = Object.keys(bookCopies).sort();

// Write function getCopiesFromMap(title) to return copies from bookCopies
// Write function listBooksInOrder() to return sortedBooks
// Your code here

Hint

Use simple functions that access the object and return the sorted array.

4

Print copies and ordered book list

Print the number of copies for the book '1984' using getCopiesFromMap('1984'). Then print the list of books in alphabetical order using listBooksInOrder()

DSA Typescript

const bookCopies = {
  'The Hobbit': 5,
  '1984': 8,
  'Brave New World': 3,
  'Fahrenheit 451': 6
};

const sortedBooks = Object.keys(bookCopies).sort();

function getCopiesFromMap(title: string): number {
  return bookCopies[title];
}

function listBooksInOrder(): string[] {
  return sortedBooks;
}

// Print copies of '1984'
// Print list of books in order
// Your code here

Hint

Use console.log to print the results of the function calls.

Practice

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

easy

A. Binary Search Tree (BST)

B. Hash Map

C. Stack

D. Queue

Solution

1. Step 1: Understand the requirement for sorted order and range queries

   Maintaining sorted order and performing range queries require a data structure that keeps elements ordered.

2. Step 2: Compare BST and Hash Map capabilities

   BST keeps elements sorted and supports efficient range queries, while Hash Map does not maintain order.

3. Final Answer:

   Binary Search Tree (BST) -> Option A

4. Quick Check:

   Sorted order + range queries = BST [OK]

Hint: Sorted order needs BST, not Hash Map [OK]

Common Mistakes:

• Thinking Hash Map maintains order
• Confusing range queries with simple lookups
• Assuming Stack or Queue can maintain sorted data

2. Which of the following is the correct TypeScript syntax to declare a Hash Map with string keys and number values?

easy

A. const map: Map = new Map();

B. const map: HashMap = new HashMap();

C. const map: Object = {};

D. const map: Map = new Map();

Solution

1. Step 1: Identify the correct TypeScript Map declaration

   TypeScript uses Map for hash maps, where K is key type and V is value type.

2. Step 2: Check each option's syntax

   const map: Map = new Map(); correctly declares a Map with string keys and number values. const map: HashMap = new HashMap(); uses a non-existent HashMap type. const map: Map = new Map(); swaps key and value types. const map: Object = {}; uses Object incorrectly.

3. Final Answer:

   const map: Map<string, number> = new Map(); -> Option D

4. Quick Check:

   Map<string, number> syntax correct [OK]

Hint: Use Map for hash maps in TypeScript [OK]

Common Mistakes:

• Using non-existent HashMap type
• Swapping key and value types
• Using plain Object without type safety

3. Consider the following TypeScript code using a BST and a Hash Map:

class Node {
  value: number;
  left: Node | null = null;
  right: Node | null = null;
  constructor(value: number) { this.value = value; }
}

class BST {
  root: Node | null = null;
  insert(value: number) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }
  inorder(node: Node | null, result: number[]) {
    if (!node) return;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
  }
}

const bst = new BST();
bst.insert(3);
bst.insert(1);
bst.insert(4);

const map = new Map();
map.set(3, 'three');
map.set(1, 'one');
map.set(4, 'four');

const bstResult: number[] = [];
bst.inorder(bst.root, bstResult);

console.log(bstResult);
console.log(Array.from(map.keys()));

What will be the output?

medium

A. [1, 3, 4]
[3, 1, 4]

B. [3, 1, 4]
[1, 3, 4]

C. [1, 3, 4]
[1, 3, 4]

D. [3, 4, 1]
[3, 4, 1]

Solution

1. Step 1: Trace BST inorder traversal output

   Inorder traversal visits nodes in ascending order: 1, 3, 4.

2. Step 2: Trace Map keys insertion order

   Map keys are iterated in insertion order: 3, 1, 4.

3. Final Answer:

   [1, 3, 4] [3, 1, 4] -> Option A

4. Quick Check:

   BST inorder sorted, Map keys insertion order [OK]

Hint: BST inorder sorts; Map keys keep insertion order [OK]

Common Mistakes:

• Assuming Map keys are sorted
• Confusing preorder with inorder traversal
• Expecting Map keys to be sorted automatically

4. The following TypeScript code attempts to insert keys into a BST and a Hash Map. It throws an error. What is the bug?

class BSTNode {
  value: number;
  left: BSTNode | null = null;
  right: BSTNode | null = null;
  constructor(value: number) { this.value = value; }
}

class BST {
  root: BSTNode | null = null;
  insert(value: number) {
    const newNode = new BSTNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (current) {
      if (value < current.value) {
        current = current.left!;
      } else {
        current = current.right!;
      }
    }
  }
}

const bst = new BST();
bst.insert(5);
bst.insert(3);

const map = new Map();
map.set(5, 'five');
map.set(3, 'three');

medium

A. The Map is not initialized properly.

B. Map keys must be strings, not numbers.

C. The insert method does not link new nodes to the tree, causing infinite loop or error.

D. BSTNode class is missing a parent pointer.

Solution

1. Step 1: Analyze BST insert method loop

   The loop moves current to left or right child but never assigns newNode to any child, so tree structure is not updated.

2. Step 2: Understand consequences of missing link

   Without linking newNode, the loop continues infinitely or tries to access null with non-null assertion, causing error.

3. Final Answer:

   The insert method does not link new nodes to the tree, causing infinite loop or error. -> Option C

4. Quick Check:

   Missing child assignment causes error [OK]

Hint: Always link new nodes to parent in BST insert [OK]

Common Mistakes:

• Ignoring the need to assign newNode to left/right
• Thinking Map keys must be strings
• Assuming parent pointer is mandatory

5. You need to store a large dataset of user scores that must be retrieved in sorted order and also allow fast lookup by user ID. Which combination of data structures is best to optimize both requirements?

hard

A. Use only a Hash Map with user ID as key and score as value

B. Use a Hash Map for user ID to score and a Balanced BST for scores with user IDs

C. Use only a BST with user ID as key and score as value

D. Use an array sorted by score and a Hash Map for user ID

Solution

1. Step 1: Identify requirements for sorted retrieval and fast lookup

   Sorted retrieval by score needs a structure that keeps order, fast lookup by user ID needs quick key access.

2. Step 2: Evaluate data structure combinations

   Hash Map gives O(1) lookup by user ID. Balanced BST keeps scores sorted and can store user IDs. Combining both meets both needs efficiently.

3. Step 3: Reject other options

   Only Hash Map lacks sorted order. Only BST with user ID key sorts by ID, not score. Array sorting is costly on updates.

4. Final Answer:

   Use a Hash Map for user ID to score and a Balanced BST for scores with user IDs -> Option B

5. Quick Check:

   Combine Hash Map + BST for lookup + sorted order [OK]

Hint: Combine Hash Map for lookup and BST for sorting [OK]

Common Mistakes:

• Using only one structure and missing one requirement
• Sorting array repeatedly on updates
• Using BST keyed by user ID instead of score