BST vs Hash Map Trade-offs for Ordered Data in DSA Javascript - Key Differences

Recall & Review

beginner

What is a key advantage of a Binary Search Tree (BST) over a Hash Map when working with ordered data?

A BST maintains elements in sorted order, allowing efficient in-order traversal to access data in ascending or descending order.

beginner

Why might a Hash Map be faster than a BST for simple key-value lookups?

Hash Maps provide average O(1) time complexity for lookups by using a hash function, while BSTs have O(log n) time complexity in balanced cases.

intermediate

What is a major drawback of using a Hash Map when you need to retrieve data in sorted order?

Hash Maps do not maintain any order of keys, so retrieving data in sorted order requires extra steps like sorting keys separately.

intermediate

How does a balanced BST ensure efficient operations compared to an unbalanced BST?

A balanced BST keeps its height minimal (around log n), ensuring operations like search, insert, and delete stay efficient at O(log n) time.

beginner

In what scenario would you prefer a Hash Map over a BST?

When you need very fast key-based access and do not care about the order of elements, a Hash Map is preferred.

Which data structure maintains elements in sorted order by default?

A Binary Search Tree

B Hash Map

C Stack

D Queue

A Binary Search Tree keeps elements sorted by key, allowing ordered traversal.

What is the average time complexity for lookup in a Hash Map?

A O(1)

B O(log n)

C O(n)

D O(n log n)

Hash Maps provide average constant time O(1) lookup using hashing.

Why might a BST be less efficient than a Hash Map for lookups?

A BSTs do not store keys

B BSTs require sorting after lookup

C BSTs have O(n) lookup time

D BSTs have O(log n) lookup time which is slower than Hash Map's O(1)

BST lookups take O(log n) time in balanced trees, slower than Hash Map's average O(1).

Which data structure is better for retrieving data in sorted order without extra processing?

A Hash Map

B Binary Search Tree

C Array

D Linked List

BSTs maintain sorted order, enabling direct in-order traversal.

What is a common disadvantage of an unbalanced BST?

A It cannot store duplicate keys

B It uses too much memory

C It can degrade to O(n) time for operations

D It does not allow traversal

An unbalanced BST can become like a linked list, causing operations to take O(n) time.

Explain the trade-offs between using a Binary Search Tree and a Hash Map for storing and retrieving ordered data.

Think about order maintenance and lookup speed differences.

Describe scenarios where a Hash Map is preferred over a BST and vice versa.

Consider the importance of order and speed in your use case.