Lecture 20:

Binary Search Trees

CS 136: Spring 2024

Katie Keith

Record on Zoom

• Lab 6 this week: No starter code!
• Recommended to allocate a bit more time for this lab
• TA eval form (Due Fri April 18) : https://forms.gle/sbqCGVLAFnhUQ4i39
• Colloquium this Friday: Dr. Ellie Pavlick

📣 Announcements

📚Readings

• Sedgewick and Wayne. Algorithms. Section 3.2.

• Wrap-Up Symbol Table Data Structure #2: Two arrays (sorted)
• Overview of Binary Search Trees (BST)
• BST get operation
• BST put operation

​

🎯 Today’s Learning Objectives

Review: Symbol Table

A symbol table is an ADT where we save information (a value) that we can later search for and retrieve by specifying a key. Keys are unique (no duplicates).

Running Example:

​

Record the number of gold medals each country won in the 2024 Olympics

Julien Alfred Wins Saint Lucia's First Gold Medal in the 100 M Dash

​

Review: Python Dictionaries are Symbol Tables

gold_medals = {

"USA": 40,

"China": 40,

"Japan": 20,

"Saint Lucia": 1,

}

gold_medals["New Zealand"] = 10

print(gold_medals["USA"])

​

​

​

put operation

get operation (search!)

Key of a dictionary

Value of a dictionary

CS 134: How do we use dictionaries?

​

CS 136: How do we implement dictionaries “under the hood”?

Multiple data structures can implement the same ADT

Binary Search Tree

Data Structures

Linked List

Hash Tables

​

List

Finite number of elements

(same element may occur more than once)

Two arrays (sorted)

Stack

Last in first out (LIFO) operations

Symbol Table

Associates a key with a value

Graph

A set of vertices, pairs of which are connected by edges

Queue

First in first out (FIFO) operations

String[] keys;

int[] values;

ADT

LinkedListST.java

​

put

💻

Analysis of Symbol Table’s Data Structures

Analysis of Symbol Table’s Data Structures

Preview for Binary Search Trees: Can we do better for put?

• Wrap-Up Symbol Table Data Structure #2: Two arrays (sorted)
• Overview of Binary Search Trees (BST)
• BST put operation
• BST get operation

​

✅

🎯 Today’s Learning Objectives

Binary Trees

A binary tree consists of nodes and links. Each node has two exactly two links and two “children” nodes.

(upside down tree)

root node

node that is the right child of root

a left link

a right link

null links

a subtree

Binary Search Tree

For a binary search tree, each key in any node is

• Larger than the keys in all nodes in that node’s left subtree
• Smaller than keys in all nodes in that node’s right subtree

root node

the key of this node is 'E'

'A' < 'E' && 'C' < 'E'

'R' > 'E' && 'H' > 'E'

left subtree

right subtree

Binary Search Tree to implement a Symbol Table

To implement a Symbol Table with a Binary Search Tree:

• The keys of nodes still obey the left subtree/right subtree ordering
• And nodes also have an associated value.

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Binary Search Tree: Inner Node Class

public class BST<Key, Value> implements SymbolTable<Key, Value> {

private Node root; // root node of BST

private int numPairs; // number of key-value pairs in the symbol table

​

private class Node {

private Key key; // BSTs maintain left/right subtree ordering by key

private Value val; // value for the node

private Node left; // node at the beginning of the left subtree

private Node right; // node at the beginning of the right subtree

...

​

The beginning of a Java implementation of a Binary Search Tree

1. What will mystery(root) print for the example below?
2. In general, what is this method doing?

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

💡Think-pair-share

• Wrap-Up Symbol Table Data Structure #2: Two arrays (sorted)
• Overview of Binary Search Trees (BST)
• BST get operation
• BST put operation

​

✅

✅

🎯 Today’s Learning Objectives

BST get (psuedocode)

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

• If the target is less than the key at the current node, move to the left subtree.
• Else if the target is greater than the key at the current node, move to the right subtree.
• Else if the target equals the key at the current node, return the value (search hit)
• Else return null (search miss)

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Can implement either recursively (in most classic implementations) or iteratively

BST get example, search hit

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Example: Search for ‘C’ (search hit).

• If the target is less than the key at the current node, move to the left subtree.
• Else if the target is greater than the key at the current node, move to the right subtree.
• Else if the target equals the key at the current node, return the value (search hit)
• Else return null (search miss)

BST get example, search miss

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

• If the target is less than the key at the current node, move to the left subtree.
• Else if the target is greater than the key at the current node, move to the right subtree.
• Else if the target equals the key at the current node, return the value (search hit)
• Else return null (search miss)

Example: Search for ‘Q’ (search miss).

• Wrap-Up Symbol Table Data Structure #2: Two arrays (sorted)
• Overview of Binary Search Trees (BST)
• BST get operation
• BST put operation
• BST analysis

​

✅

✅

✅

🎯 Today’s Learning Objectives

BST put example

BST<Character, Integer> bst = new BST<Character, Integer>();

bst.put(‘S’, 30);

bst.put(‘E’, 105);

…

​

bst.put(‘L’, 76);

Q: Where should we insert the ‘L’ key?

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

BST put example

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Step 1. Search for ‘L’. This ends in a null link.

BST<Character, Integer> bst = new BST<Character, Integer>();

bst.put(‘S’, 30);

bst.put(‘E’, 105);

…

​

bst.put(‘L’, 76);

BST put example

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Step 1. Search for ‘L’. This ends in a null link.

​

Step 2. Create new node and update the link of the parent node.

'L’

76

BST<Character, Integer> bst = new BST<Character, Integer>();

bst.put(‘S’, 30);

bst.put(‘E’, 105);

…

​

bst.put(‘L’, 76);

BST put algorithm example (key already exists)

BST<Character, Integer> bst = new BST<Character, Integer>();

bst.put(‘S’, 30);

bst.put(‘E’, 105);

…

​

bst.put(‘L’, 76);

bst.put(‘A’, 100);

​

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Step 1. Search for ‘A’. This ends in a node that already exists.

​

Step 2. Update the value at that node.

'L’

76

• Wrap-Up Symbol Table Data Structure #2: Two arrays (sorted)
• Overview of Binary Search Trees (BST)
• BST get operation
• BST put operation
• BST analysis

​

✅

✅

✅

✅

🎯 Today’s Learning Objectives

Suppose we are searching target key, T. How many comparisons (comparing target T to another node’s key) will be made for each of the following binary search trees?

Tree 2

Tree 1

Tree 3

Notes:

• The same 7 nodes are in each of the three trees
• T is a character (not a generic 🤣)

💡Think-pair-share

Binary Search Trees

Advantages:

• BSTs allow us to keep the keys in order which makes sorting easy and cheap
• On average, put and get are O(log n) (a balanced BST)
• In-order traversal (in ascending order) is O(n)

Disadvantages:

• The running times of BST algorithms depend on the tree’s shape (balanced?), which, in turn, depend on the order in which keys are inserted.
• Worse case for put and get is still O(n)

Analysis of Symbol Table’s Data Structures

• Wrap-Up Symbol Table Data Structure #2: Two arrays (sorted)
• Overview of Binary Search Trees (BST)
• BST get operation
• BST put operation
• BST analysis

​

✅

✅

✅

✅

✅

🎯 Today’s Learning Objectives

• What will mystery(root) print for the example below?
• In general, what is this method doing?

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Answer

💡Think-pair-share

Review: Call Stack (Lecture 12)

A call stack tracks method calls during program execution

• Method call: push stack frame (local environment and return address)
• Method finishes execution (e.g., returns) : pop stack frame

​

Example:

Call stack: LIFO, Last method called is the first to be completed and removed from the stack

public static int fib(int n) {

if (n == 0|| n == 1) {

return n;

} else {

return fib(n - 1) + fib(n - 2);

}

}

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

Call stack: LIFO

>>

Values of local variables for this stack frame

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>>

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>>

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>>

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>>

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>>

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Execution finishes so we pop this stack frame

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>>

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Control flow moves back to stack frame with node ‘A’

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Execution finishes so we pop this stack frame

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Execution finishes so we pop this stack frame

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Execution finishes so we pop this stack frame

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Control flow moves back to method call with node ‘E’

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12 105

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12 105

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Call stack: LIFO

💡Think-pair-share

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12 105

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

​

Many more method calls later…

Call stack: LIFO

💡Think-pair-share

'E'

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

>> 35 12 105 24 45 30 106

Many more method calls later…

A

C

E

H

R

S

X

Call stack: LIFO

💡Think-pair-share

• What will mystery(root) print for the example below?
• In general, what is this method doing?

​

public static void mystery(Node x) {

if (x != null) {

mystery(x.left);

System.out.print(x.val + " ");

mystery(x.right);

}

}

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

Answer #1:

>> 35 12 105 24 45 30 106

A

C

E

H

R

S

X

Answer #2: In-order traversal of keys (ascending/alphabetical order) and printing their corresponding values

​

💡Think-pair-share