1 of 30

BSTMap (Binary Search Trees)

Lab 6

CS61B Spring 2025

2 of 30

Announcements

  • Midterm 2 Alterations Request is due Friday, 3/21
    • Late requests will not be accepted

​

  • Tutor Review Session 2 is this Friday, 3/7 in Soda Labs
    • Midterm 2 Revision, Part 1!
    • Will be covering ADTs, BSTs, Disjoint Sets, and Asymptotics

​

  • HW2 is due on Friday, 03/07
    • Get started early!

​

  • Project 2A is due on Wed, 3/12

​

​

​

​

​

CS61B Spring 2025

3 of 30

Binary Search Trees

CS61B Spring 2025

4 of 30

Binary Search Trees

Given a sorted array, we’re able to achieve a runtime of log(N) when searching for a specific element in the array (why?).

  • Note that we’re able to achieve such a runtime under the assumption that we already have a sorted array. This is where binary search trees come in!

CS61B Spring 2025

5 of 30

Binary Search Trees

With binary search trees, we can take advantage of a tree structure while adding in some additional conditions to maintain the elements in a “sorted” order.

  • By adding in additional constraints, we can determine how elements are placed into our tree structure, allowing us to effectively make it much faster to insert, lookup and remove items.

​

CS61B Spring 2025

6 of 30

Binary Search Tree Def.

As the name implies, binary search trees are just binary trees, so the properties of a binary tree still applies (each node has at most 2 children).

​

CS61B Spring 2025

7 of 30

Binary Search Tree Def.

As the name implies, binary search trees are just binary trees, so the properties of a binary tree still applies (each node has at most 2 children).

​

The specific BST properties are as the following:

  • Assume that we are at node X
    • Every value in X’s left subtree is smaller than X
    • Every value in X’s right subtree is greater than X

CS61B Spring 2025

8 of 30

Insertion

To maintain the properties of the BST, let’s consider how we insert an element T (assume no duplicates)

CS61B Spring 2025

9 of 30

Insertion

To maintain the properties of the BST, let’s consider how we insert an element T (assume no duplicates)

  • We compare the value of T to the value in the current node (starting at the root)
    • If T is smaller than the current node’s value, we go to the left subtree
    • If T is larger than the current node’s value, we go the right subtree
    • We repeat this until we can insert T as a leaf node.
  • Note that the left and right subtrees are both BSTs themselves!

CS61B Spring 2025

10 of 30

Insertion Demo

CS61B Spring 2025

11 of 30

BST Insertion

14

Starting out, let’s say we’ve inserted 14 into our binary search tree. So 14 is the root of our tree.

CS61B Spring 2025

12 of 30

14

10

Next to insert.

10

BST Insertion

Now let’s insert a number into the binary search tree. We’ll go with 10.

​

At this point, we need to figure how where 10 goes in the binary search tree. To do so, we want to make a comparison between 10 and 14.

​

CS61B Spring 2025

13 of 30

14

14

10

20

Next to insert.

BST Insertion

Since 10 is less than 14, we go to the left. Since 14 has no children so far, 10 can be inserted as leaf node to the left.

​

Now let’s insert 20 into our tree and repeat the same process.

CS61B Spring 2025

14 of 30

14

14

20

10

23

5

4

Next to insert.

Since 20 is greater than 14, it will be inserted into the tree to the right of 14.

​

What will our tree look like if we inserted these numbers in this order: 4, 5, 23?

BST Insertion

CS61B Spring 2025

15 of 30

14

14

20

10

23

5

Next to insert.

Since 20 is greater than 14, it will be inserted into the tree to the right of 14.

​

What will our tree look like if we inserted these numbers in this order: 4, 5, 23?

BST Insertion

4

CS61B Spring 2025

16 of 30

14

14

20

10

23

Next to insert.

Since 20 is greater than 14, it will be inserted into the tree to the right of 14.

​

What will our tree look like if we inserted these numbers in this order: 4, 5, 23?

BST Insertion

4

5

CS61B Spring 2025

17 of 30

14

14

20

23

5

4

10

It’ll look something like this!

​

When inserting an item, we make comparisons with the current node we’re on to determine which way we traverse down the binary search tree.

​

Once we hit a leaf node, we place our item there.

BST Insertion

CS61B Spring 2025

18 of 30

Quick Tip

Recursion is your best friend!

  • Remember, the left or right subtree of any node is also a BST!
    • When we’re traversing through the tree (top-down), we know that the value is going to either be smaller or larger than the current value we are currently on. Based on this, we can traverse either the left subtree or right subtree (hint!).

CS61B Spring 2025

19 of 30

Quick Tip

Recursion is your best friend!

  • Remember, the left or right subtree of any node is also a BST!
    • When we’re traversing through the tree (top-down), we know that the value is going to either be smaller or larger than the current value we are currently on. Based on this, we can traverse either the left subtree or right subtree (hint!).

Avoid “arms-length” recursion!

  • Don’t stop when the base case is one step away from the actual base case
  • i.e., T.left == null instead of T == null

CS61B Spring 2025

20 of 30

One Last Important Thing

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

21 of 30

One Last Important Thing

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

22 of 30

One Last Important Thing

14

14

20

23

27

34

Suppose we had the following spindly tree:

​

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

​

​

CS61B Spring 2025

23 of 30

One Last Important Thing

Suppose we had the following spindly tree:

​

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

​

Worst case, O(N). Why?

​

​

14

14

20

23

27

34

CS61B Spring 2025

24 of 30

Lab Overview

CS61B Spring 2025

25 of 30

An Overview

Lab 06 is due Friday, 03/07 at 11:59 pm.

  • As a reminder, to get the lab assignment, run git pull skeleton main in your personal repository.

​

Deliverables:

  • Complete your implementation of BSTMap and ensure that it implements the interface Map61B.
  • Make sure to fill out speedTestResults.txt sufficiently, noting your observations down.
  • Some tips:
    • We highly recommend you have some helper methods - they’ll reduce the amount of code you need to write.
    • Think recursively!

CS61B Spring 2025

26 of 30

Lab Notes

CS61B Spring 2025

27 of 30

Lab Notes

printInorder(): Here’s a reminder of the pseudocode for in-order traversal of a binary tree

public void inOrder(Node node) {

if (node == null) {

return;

}

inOrder(node.left);

processNode(node);

inOrder(node.right);

}

CS61B Spring 2025

28 of 30

Lab Notes

Another thing to note in this lab is that in your implementation, you should ensure that generic keys K in BSTMap<K, V> extends Comparable.

​

This is to make sure that you’re able to use the compareTo method in your implementation, specifically with K (why might that be useful?).

​

CS61B Spring 2025

29 of 30

public class BSTSet<K extends Comparable<K>> implements Set61B<K> {...}

In this lab, your generic key K needs to implement Comparable. The above shows an example of what that may look like - the main difference being that your BSTMap takes <K, V> instead.

​

CS61B Spring 2025

30 of 30

Attendance

https://forms.gle/jk9dZ1hLyBRsBqFMA

​

CS61B Spring 2025