BST, Heaps & Map - DSA Interview Questions

Binary Search Trees (BST), Heaps, and Maps are fundamental data structures used for efficient searching, sorting, and storage of data. BSTs provide fast insertion, deletion, and search operations, Heaps enable priority-based data access, and Maps (HashMaps, TreeMaps) offer quick key-based retrieval. Mastering these structures is crucial for optimizing performance in complex coding problems.

Practice BST, Heaps & Map DSA Coding Problems with Solutions

Learning Objectives:

Understand the applications of BST, Heaps, and Maps in solving common programming challenges efficiently. Learn how to implement and optimize operations such as insertion, deletion, searching, and sorting using these data structures.

Exercise Instructions:

Start with the first problem and attempt to solve it before checking the hint or solution.
Ensure you understand the logic behind each solution, as this will help you with more complex problems.
Use these exercises to reinforce your learning and identify areas that may require further study.

1. Insert a Node in a Binary Search Tree

Required Input:

root = [4, 2, 7, 1, 3] val = 5

Expected Output:

[4, 2, 7, 1, 3, 5]

Code In Python

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def insert_into_bst(root, val): # Write your logic here pass # Prefilled input root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7)) val = 5 print(insert_into_bst(root, val))

Run Code?

Click Run Button to view compiled output

2. Search for a Value in a BST

Required Input:

root = [4, 2, 7, 1, 3] target = 2

Expected Output:

Code In Python

def search_bst(root, target): # Write your logic here pass # Prefilled input root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7)) target = 2 print(search_bst(root, target))

Run Code?

Click Run Button to view compiled output

3. Find the Minimum and Maximum Value in a BST

Required Input:

root = [4, 2, 7, 1, 3]

Expected Output:

Minimum: 1 Maximum: 7

Code In Python

def find_min_max(root): # Write your logic here pass # Prefilled input root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7)) print(find_min_max(root))

Run Code?

Click Run Button to view compiled output

4. Find the Inorder Successor of a Node in a BST

Required Input:

root = [20, 9, 25, 5, 12, None, None, None, None, 11, 14] target = 9

Expected Output:

Code In Python

def inorder_successor(root, target): # Write your logic here pass # Prefilled input root = TreeNode(20, TreeNode(9, TreeNode(5), TreeNode(12, TreeNode(11), TreeNode(14))), TreeNode(25)) target = 9 print(inorder_successor(root, target))

Run Code?

Click Run Button to view compiled output

5. Implement a Min Heap from Scratch

Required Input:

operations = ['insert 5', 'insert 3', 'insert 8', 'extract_min', 'get_min']

Expected Output:

3
5

Code In Python

class MinHeap: def __init__(self): # Write your logic here pass def insert(self, x): pass def extract_min(self): pass def get_min(self): pass # Prefilled input heap = MinHeap() operations = ['insert 5', 'insert 3', 'insert 8', 'extract_min', 'get_min'] for op in operations: if 'insert' in op: heap.insert(int(op.split()[1])) elif op == 'extract_min': print(heap.extract_min()) elif op == 'get_min': print(heap.get_min())

Run Code?

Click Run Button to view compiled output

6. Find the First Non-Repeating Character in a String Using a HashMap

Required Input:

s = 'swiss'

Expected Output:

Code In Python

def first_non_repeating(s): # Write your logic here pass # Prefilled input s = 'swiss' print(first_non_repeating(s))

Run Code?

Click Run Button to view compiled output

7. Implement a Max Heap from Scratch

Required Input:

operations = ['insert 10', 'insert 15', 'insert 5', 'extract_max', 'get_max']

Expected Output:

15
10

Code In Python

class MaxHeap: def __init__(self): # Write your logic here pass def insert(self, x): pass def extract_max(self): pass def get_max(self): pass # Prefilled input heap = MaxHeap() operations = ['insert 10', 'insert 15', 'insert 5', 'extract_max', 'get_max'] for op in operations: if 'insert' in op: heap.insert(int(op.split()[1])) elif op == 'extract_max': print(heap.extract_max()) elif op == 'get_max': print(heap.get_max())

Run Code?

Click Run Button to view compiled output

8. Find the K Smallest Elements in an Array Using a Min Heap

Required Input:

arr = [7, 10, 4, 3, 20, 15] k = 3

Expected Output:

[3, 4, 7]

Code In Python

import heapq def k_smallest_elements(arr, k): # Write your logic here pass # Prefilled input arr = [7, 10, 4, 3, 20, 15] k = 3 print(k_smallest_elements(arr, k))

Run Code?

Click Run Button to view compiled output

9. Find the Most Frequent Element in an Array Using a HashMap

Required Input:

arr = [1, 3, 2, 1, 4, 1, 3, 2, 3, 3, 3]

Expected Output:

Code In Python

from collections import Counter def most_frequent_element(arr): # Write your logic here pass # Prefilled input arr = [1, 3, 2, 1, 4, 1, 3, 2, 3, 3, 3] print(most_frequent_element(arr))

Run Code?

Click Run Button to view compiled output

10. Find the K Largest Elements in an Array Using a Max Heap

Required Input:

arr = [7, 10, 4, 3, 20, 15] k = 3

Expected Output:

[20, 15, 10]

Code In Python

import heapq def k_largest_elements(arr, k): # Write your logic here pass # Prefilled input arr = [7, 10, 4, 3, 20, 15] k = 3 print(k_largest_elements(arr, k))

Run Code?

Click Run Button to view compiled output

1 of 3