Homework 9: BSTMap

Assignment Intro Section 5

CS61B Spring 2025

CS 61B Fall 2025

Announcements

CS61B Spring 2025

CS 61B Fall 2025

Content Review: Why BSTs?

CS 61B Fall 2025

CS61B Spring 2025

CS 61B Fall 2025

Maps

As a refresher, Maps store key-value pairs, where each unique key is mapped to a value.

“biology”

“green”

“math”

“blue”

“english”

“red”

“history”

“purple”

“chemistry”

“green”

Map<String, String>

CS61B Spring 2025

CS 61B Fall 2025

Maps

As a refresher, Maps store key-value pairs, where each unique key is mapped to a value.

“biology”

“green”

“math”

“blue”

“english”

“red”

“history”

“purple”

“chemistry”

“green”

Map<String, String>

Notice:

Two keys can be mapped to the same value, but the same key cannot exist twice in a Map.

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

It’s pretty clear why maps are a useful data structure. Being able to store a relationship between one object (a key) and another (its associated value) has many applications:

• Mapping high school subjects to their objectively correct associated folder colors
• Given some Student objects, mapping studentIds to their associated Student
• In the case of a dictionary, mapping words to their definitions
• …and many, many more!

There are a variety of ways we could go about building a Map. Why not try a backing List?

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

When picking an architecture for our Map, we want to optimize the time it takes to access elements using a key.

​

​

​

​

​

Discussion question: what are some reasons this architecture might not be optimal for building a Map?

MapNode

“biology”

“green”

MapNode

“math”

“blue”

MapNode

“english”

“red”

MapNode

“history”

“purple”

MapNode

“math”

“blue”

MapNode

“music”

“black”

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

For one, in the worst case, retrieving a value given a key takes O(n) time (where n is the number of key-value pairs in the Map). For such a common operation, this is not optimal.

​

​

​

​

​

​

MapNode

“biology”

“green”

MapNode

“math”

“blue”

MapNode

“english”

“red”

MapNode

“history”

“purple”

MapNode

“math”

“blue”

MapNode

“music”

“black”

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

For one, in the worst case, retrieving a value given a key takes O(n) time (where n is the number of key-value pairs in the Map). For such a common operation, this is not optimal.

​

​

​

​

​

Additionally, Maps should never have duplicate keys. Lists can have duplicates, so, assuming we have to check the entire list for every put operation, adding items to the Map runs in Θ(n).

MapNode

“biology”

“green”

MapNode

“math”

“blue”

MapNode

“english”

“red”

MapNode

“history”

“purple”

MapNode

“math”

“blue”

MapNode

“music”

“black”

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

Switching our backing data structure to a BST solves both of these problems.

First, search time decreases significantly on average.

Discussion questions:

1. How do you go about searching for an element in a BST?
2. In the best case, what is its asymptotic runtime?

4

Math 56

2

Math 1B

6

Math 110

1

Math 1A

3

Math 53

5

Math 55

7

Math 104

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

Search process begins at the root:

• compare our desired key to the key of the node we’re currently on
• If our desired key is less than the current node, we traverse left.
• If our desired key is greater than the current node, we traverse right.
• Due to the BST property, we can do this recursively!

4

Math 56

2

Math 1B

6

Math 110

1

Math 1A

3

Math 53

5

Math 55

7

Math 104

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

Search process begins at the root:

• compare our desired key to the key of the node we’re currently on
• If our desired key is less than the current node, we traverse left.
• If our desired key is greater than the current node, we traverse right.
• Due to the BST property, we can do this recursively!

4

Math 56

2

Math 1B

6

Math 110

1

Math 1A

3

Math 53

5

Math 55

7

Math 104

get(5)

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

Search process begins at the root:

• compare our desired key to the key of the node we’re currently on
• If our desired key is less than the current node, we traverse left.
• If our desired key is greater than the current node, we traverse right.
• Due to the BST property, we can do this recursively!

4

Math 56

2

Math 1B

6

Math 110

1

Math 1A

3

Math 53

5

Math 55

7

Math 104

get(5)

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

Search process begins at the root:

• compare our desired key to the key of the node we’re currently on
• If our desired key is less than the current node, we traverse left.
• If our desired key is greater than the current node, we traverse right.
• Due to the BST property, we can do this recursively!

4

Math 56

2

Math 1B

6

Math 110

1

Math 1A

3

Math 53

5

Math 55

7

Math 104

get(5)

// Returns “Math 55”

CS61B Spring 2025

CS 61B Fall 2025

Why BSTs?

Our previously-slow addition time also speeds up! BSTs can’t contain duplicate keys, so they’re better suited to a Map.

Think to yourself:

1. What algorithm do we run to add a new key?
2. How does this change if we find that the key is already in the BST?

4

Math 56

2

Math 1B

6

Math 110

1

Math 1A

3

Math 53

5

Math 55

7

Math 104

CS61B Spring 2025

CS 61B Fall 2025

Runtime Considerations

How does the order of elements inserted into the BST affect the runtime of it (think about the structure that can be created)?

• Are we always guaranteed to have a worst case runtime of log(N) if we’re looking up an element in the BST?

CS61B Spring 2025

CS 61B Fall 2025

Runtime Considerations

How does the order of elements inserted into the BST affect the runtime of it (think about the structure that can be created)?

• Are we always guaranteed to have a worst case runtime of log(N) if we’re looking up an element in the BST?

​

Nope! The insertion of elements can affect our worst case runtime for lookup (i.e. a bushy tree structure is O(log(N)) while a spindly tree is O(N)).

​

​

​

​

CS61B Spring 2025

CS 61B Fall 2025

Runtime Considerations

Suppose we had the following spindly tree:

​

What would be the runtime of containsKey(10) be?

​

​

4

Math 56

6

Math 110

7

Math 104

10

Math 212

CS61B Spring 2025

CS 61B Fall 2025

Runtime Considerations

Suppose we had the following spindly tree:

​

What would be the runtime of containsKey(34) be?

​

Worst case, O(N). Why?

4

Math 56

6

Math 110

7

Math 104

10

Math 212

CS61B Spring 2025

CS 61B Fall 2025

Lab Overview

CS 61B Fall 2025

CS61B Spring 2025

CS 61B Fall 2025

Deliverables

Homework 9 is due this Friday, October 10th at 11:59PM on Gradescope.

Complete the following tasks:

• Task 1: BSTMap
• Task 2: How Fast Is It?

As usual, pull from the skeleton to get the skeleton code!

CS61B Spring 2025

CS 61B Fall 2025

Extra Tip: Implementing printInOrder

You may have heard of the following 3 tree traversals: pre-order, in-order, and post-order (don’t worry if not, will be covered in lecture next week).

Which one of these traversals prints out the elements of a BST from least to greatest?

CS61B Spring 2025

CS 61B Fall 2025

Extra Tip: Implementing printInOrder

You may have heard of the following 3 tree traversals: pre-order, in-order, and post-order (don’t worry if not, will be covered in lecture next week).

Which one of these traversals prints out the elements of a BST from least to greatest?

void inOrder(Node node) {

return if node is null

inOrder(node.left)

processNode(node)

inOrder(node.right)

}

CS61B Spring 2025

CS 61B Fall 2025