Lauren's DS210 Materials

Activity 35 - Binary Heap and BST practice

Problem 1: Heap validation

Tree 1:         Tree 2:         Tree 3:
    42              50              30
   /  \            /  \            /  \
  30  25          30  35          25  20
 / \  /          / \    \        /  
10 20 15        25 40   20      15

Tree 4:         Tree 5:
    100             60
   /  \            /  \
  80  90          50  55
 /      \        /  \
50      85      40  45

Questions:

1. Which are valid max-heaps?
2. For invalid ones, identify the heap property violation
3. What is the array representation of Tree 1?

Problem 2: Tracing heap operations

For each task, draw a representation of the process used and the final heap.

Starting max-heap:

       42
      /  \
    35    25
   / \    /
  30 20  15

Tasks:

1. Insert 40: Show the bubble-up process.
2. Extract-max: Show the bubble-down process
3. Insert 50: Show the bubble-up process.
4. What is the time complexity of each operation?

Problem 3: BST validation

Tree 1:         Tree 2:         Tree 3:
    10              8                15
   /  \            / \              /  \
  5   15          4   10           10   20
 / \  /          / \    \         /  \   \
1  7 12         1   5   14       5   12  25
                   / \
                  3   6

Tree 4:         Tree 5:
    20              50
   /  \            /  \
  10  30          25  75
 /  \   \        /  \  \
5   15  25      10 30  80
               /  \
              5   40

Questions:

1. Which are valid BSTs?
2. For invalid ones, identify the violation
3. How would you fix them?

Problem 4: Tracing BST operations

In the space below, draw modified trees representing how each task would be completed, and note the time-complexity of that task.

Starting BST:

       8
      / \
     3   10
    / \    \
   1   6   14
      / \  /
     4  7 13

Tasks:

1. Trace: Search for 4 (show path)
2. Trace: Search for 11 (show path, realize not found)
3. Trace: Insert 5 (show where it goes, draw resulting tree)
4. Trace: Delete 6 (two children - find successor, show result)
5. Trace: Delete 10 (one child - show result)

Problem 5: Comparing BST and Binary Heap

1. Is it possible for a tree to satisfy both BST and heap properties? If yes, what constraints must it have? If no, why not?

2. For each problem, decide whether a BST or a Binary Heap would be better, and explain why:

a. Finding the median of a stream of numbers (maintain as numbers arrive) b. Finding the 10 largest values in a dataset of 1 million numbers c. Maintaining a sorted list where you frequently check if a value exists d. Processing tasks by priority where you only care about the highest priority task e. Implementing autocomplete where you need to find all words with a given prefix

3. Fill in this table: