Activity: Binary Search Trees

Learning Objectives:

Understand the properties of binary search trees.
Implement a search function for a binary search tree.
Analyze the time complexity of searching in a binary search tree.
Write code to manipulate binary search trees.

Time to Complete: 50 minutes

Submission: Submit individual PDF to Canvas

Instructions:

For these activities, follow the steps closely. Your goal is to complete all parts of the activity within the time provided.

If a section is hidden behind a "Continue" button, you should make sure that you have completed the previous sections and answered any questions before moving on. Do not skip ahead or reveal any solution until you have completed the previous steps.

Collaboration Encouraged

I encourage you to work with a partner or in a small group (no more than three) for in-class activities! Feel free to divvy up roles, compare solutions, and learn from each other.

If the assignment requires you to submit your work, make sure to include the names of all team members in the submission.

Your Name(s):

Part 1: Binary Search Trees

(15 min)

Consider this tree:

graph TB;
    A((8))-->B((3))
    A-->C((10))
    B-->D((1))
    B-->E((6))
    C-->F((9))
    C-->G((14))
    E-->H((4))
    E-->I((7))

Take a look at all the nodes to the left of the root.
- What is the relationship between the root and all the values to the left?
Now, take a look at all the nodes to the right of the root.
- What is the relationship between the root and all the values to the right?
Do you notice a pattern? Does this hold up for all nodes in the tree?
- What is the pattern you see?
Solutions
- All nodes to the left of a node have values less than the node's value.
- All nodes to the right of a node have values greater than the node's value.
- This pattern holds for all nodes in the tree.

This is called a binary search tree (BST). A BST is a binary tree where, for every node:
- All nodes to the left have values less than the node's value.
- All nodes to the right have values greater than the node's value.

Consider the following tree:

graph TB;
    A((8))
    B((3))
    C((9))
    D((1))
    E((6))
    F((7))
    X1((X)):::hidden

    A-->B
    A-->C
    B-->D
    B-->E
    C-->F
    C~~~X1

    classDef hidden display: none;

Is this a valid BST? Why or why not?

Solution

No, this is not a valid BST. The right subtree from the root contains a value (7) that is less than the root's value.

The power of a BST is that it allows for efficient searching. The following psuedocode shows how to search for a value in a BST:

def search(value):
    return searchHelper(root, value)

def searchHelper(node, value):
    if node is null or node.value == value:
        return node

    if value < node.value:
        return searchHelper(node.left, value)
    else:
        return searchHelper(node.right, value)

Summarize the search algorithm in your own words.

Let's do an example! Imagine we had the following tree:
```
graph TB;
    A((15))
    B((7))
    C((21))
    D((3))
    E((12))
    F((18))
    G((25))
    H((1))
    I((4))
    J((10))
    K((13))
    X1((X)):::hidden
    X2((X)):::hidden
    X3((X)):::hidden
    X4((X)):::hidden

    classDef hidden display: none;

    A-->B
    A-->C
    B-->D
    B-->E
    C-->F
    C-->G
    D-->H
    D-->I
    E-->J
    E-->K
```
- If we search for the value 12, what is the path we would take? Start at the root.
  
  Write down the sequence of nodes visited when searching for the value 12.
  
  Solution
  
  The sequence of nodes visited when searching for the value 12 is: 15, 7, 12.
- If we (try to) search for the value 2, what is the path we would take? Start at the root.
  
  Write down the sequence of nodes visited when searching for the value 2.
  
  Solution
  
  The sequence of nodes visited when searching for the value 2 is: 15, 7, 3, 1.

BSTs allow for efficient searching, just like a binary search! But unlike a binary search, which requires a sorted array, we can maintain a BST with insertions and deletions.

In the next part, we will think about the algorithms needed to create and maintain a BST.

Part 2: Creating and Maintaining a BST

(20 min)

Now, let's think about how we create and maintain a BST.

Start with this single root node:

graph TB;
    A((5))

Draw it on a sheet of paper.

If you add the value 3, where should it go?
- Update your tree to include the value 3 in a new node. Don't change any existing nodes.
Solution

Add the value 3 as the left child of the root node.

Your tree should now look like this:

graph TB;
    A((5))
    B((3))

    X1((X)):::hidden
    X2((X)):::hidden
    X3((X)):::hidden
    X4((X)):::hidden

    classDef hidden display: none;

    A-->B
    A~~~X1

Add the value 7 to the tree.
Where should the value 7 go?

Solution

Add the value 7 as the right child of the root node.

Your tree should now look like this:
```
graph TB;
    A((5))
    B((3))
    C((7))

    X1((X)):::hidden
    X2((X)):::hidden
    X3((X)):::hidden
    X4((X)):::hidden

    classDef hidden display: none;

    A-->B
    A-->C
```
- Add the value 4 to the tree. Again, don't change any existing nodes.
- Where should the value 4 go?
Solution

Add the value 4 as the right child of node 3.

Your tree should now look like this:
```
graph TB;
    A((5))
    B((3))
    C((7))
    D((4))

    X1((X)):::hidden
    X2((X)):::hidden
    X3((X)):::hidden
    X4((X)):::hidden

    classDef hidden display: none;

    A-->B
    A-->C
    B~~~X1
    B-->D
```
- Generalize the process of adding a value to a BST. What are the steps you would take to add a value to a BST?
  
  Write down the steps/psuedocode you would take to add a value to a BST.
Solution
1. Start at the root.
2. If the value is less than the current node's value, search down the left child.
3. If the value is greater than the current node's value, search down the right child.
4. Repeat steps 2 and 3 until you reach a null child.
5. Add the value as a new node at the null child.

This is the basic "insertion" operation for a BST. You can review it in the following pseudocode:

def insert(value):
    root = insertHelper(root, value)

def insertHelper(node, value):
    # Base case: found a null child, so create a new node and return it
    if node is null:
        return new Node(value)

    # Recursively set left or right child (if no nodes are created, tree is unchanged)
    if value < node.value:
        node.left = insertHelper(node.left, value)
    else:
        node.right = insertHelper(node.right, value)

    return node  # Return current node

You can review animations and an implementation of it in this article.

Start with an empty tree. Trace through the BST insertion algorithm to insert the keys 6, 5, 7, 1, 3, 2, 4 in that order.
- Draw the tree on a sheet of paper as you go.
- What is the height of the resulting tree?
- Is this tree full, complete, balanced, or perfect?
- Write down how many nodes you would have to visit to find each number from 1 to 7.
  - For example, to find 1, it would take 3 nodes: 6, 5, 1. So you would write 1: 3 nodes.
  - How many would it take to find 2, 3, 4, 5, 6, and 7?
- What is the (exact) average number of nodes you would have to visit to find a value in this tree?
  - Remember, an average case analysis is performed by adding up the costs for all possible cases, then dividing by the total number of cases.
Tree Drawing
```
graph TB;
X2((X)):::hidden
A((6))
B((5))
C((7))
D((1))
E((3))
F((2))
G((4))
X1((X)):::hidden
X3((X)):::hidden
X4((X)):::hidden

classDef hidden display: none;

A-->B
A-->C
B-->D
B~~~X1
D~~~X2
D-->E
E-->F
E-->G
```
Solutions
- The height of the resulting tree is 4.
- The tree is not full, complete, perfect, or balanced.
- The number of nodes visited to find each value is:
  - 1: 3 nodes
  - 2: 5 nodes
  - 3: 4 nodes
  - 4: 5 nodes
  - 5: 2 nodes
  - 6: 1 node
  - 7: 2 nodes
- The average number of nodes visited is \(\frac{3+5+4+5+2+1+2}{7} = \frac{22}{7} \approx 3.14\) (yay pi).

Start a new tree. Draw the BST with the smallest possible height containing the values from 1-7, in any order you choose.
- What is the height of the resulting tree?
- Is this tree full, complete, balanced, or perfect?
- Just like before, write down how many nodes you would have to visit to find each number from 1 to 7.
- What is the (exact) average number of nodes you would have to visit to find a value in this tree?
- Is this average greater or less than the previous tree?
Solutions
```
graph TB;
A((4))
B((2))
C((6))
D((1))
E((3))
F((5))
G((7))

A-->B
A-->C
B-->D
B-->E
C-->F
C-->G
```
- The height of the resulting tree is 2.
- The tree is full, complete, balanced, and perfect.
- The number of nodes visited to find each value is:
  - 1: 3 nodes
  - 2: 2 nodes
  - 3: 3 nodes
  - 4: 1 node
  - 5: 3 nodes
  - 6: 2 nodes
  - 7: 3 nodes
- The average number of nodes visited is \(\frac{3+2+3+1+3+2+3}{7} = \frac{17}{7} \approx 2.43\). This is less than the previous tree!

Take this same tree, and now answer the following questions:
- Write the order of nodes visited in a pre-order traversal.
- Write the order of nodes visited in an in-order traversal.
- Write the order of nodes visited in a post-order traversal.
- Which of these traversals gives the order in which nodes should be added to a new BST to obtain the minimum height?
Solutions
- Pre-order traversal: 4, 2, 1, 3, 6, 5, 7
- In-order traversal: 1, 2, 3, 4, 5, 6, 7
- Post-order traversal: 1, 3, 2, 5, 7, 6, 4
- The pre-order traversal gives the order in which nodes should be added to a new BST to obtain the minimum height.

This tree is an example of a best-case scenario for finding a value in a BST. The tree is balanced, and the average number of nodes visited is minimized.
- We will later analyze the exact performance of a BST, but for now, let's summarize the insertion process.

BST Insertion Summary

The insertion algorithm is a recursive algorithm that traverses the tree to find the correct location for the new node.

At each step, we compare values and update the tree as we go, e.g. node.left = insertHelper(node.left, value).
Typically, the tree won't change because we are just returning the node.
Once we find a null child, we create a new node and return it, which updates the tree.

Last, take a look at the removal algorithm.

def remove(value):
    root = removeHelper(root, value)

def removeHelper(node, value):
    if node is null:
        return null

    # Recursively search for the node to remove
    if value < node.value:
        node.left = removeHelper(node.left, value)  # Search left
    elif value > node.value:
        node.right = removeHelper(node.right, value)  # Search right
    else:

        # Found it -- multiple cases based on number of children:

        if node.left is null and node.right is null:  # No children
            return null
        elif node.left is null:  # One child (on the right)
            return node.right
        elif node.right is null:  # One child (on the left)
            return node.left
        else:  # Two children
            node.value = findMax(node.left)  # Copy the largest value from the left subtree
            node.left = removeHelper(node.left, node.value)  # Delete that node from the left subtree

    return node

Notice how similar it is to the insertion algorithm, updating the child nodes to the return value of the recursive call: node.left = removeHelper(node.left, value) and node.right = removeHelper(node.right, value).
This is important because we need to update the tree as we go. Usually, removeHelper just returns the node, meaning that the tree is unchanged. But if we want a node removed, we return a different node (or null) to update the tree.
The big part to note is the last case in the if statement, where we find the node to remove. Let's focus on that part. Removal will be difficult to understand unless you trace through the code!

There are three cases to consider when removing a node: 1. The node has no children. 2. The node has one child. 3. The node has two children.

Consider this tree with 5 nodes:

graph TB;
    A((5))
    B((3))
    C((7))
    D((2))
    E((4))

    A-->B
    A-->C
    B-->D
    B-->E

Trace through the code for remove(2). Draw the tree after removal.
Write the order of nodes visited in a pre-order traversal after removal.

Solution

graph TB;
A((5))
B((3))
C((7))
E((4))

A-->B
A-->C
B~~~X1:::hidden
B-->E

classDef hidden display: none;

Pre-order traversal: 5, 3, 4, 7

Consider the same tree:

graph TB;
    A((5))
    B((3))
    C((7))
    D((2))
    E((4))

    A-->B
    A-->C
    B-->D
    B-->E

Trace through the code for remove(3). Draw the tree after removal.
Write the order of nodes visited in a pre-order traversal after removal.

Solution

graph TB;
A((5))
B((2))
C((7))
D((4))

A-->B
A-->C
B~~~X1:::hidden
B-->D

classDef hidden display: none;

Pre-order traversal: 5, 2, 4, 7

Finally, consider the tree once more:
```
graph TB;
    A((5))
    B((3))
    C((7))
    D((2))
    E((4))

    A-->B
    A-->C
    B-->D
    B-->E
```
- Trace through the code for remove(5). Draw the tree after removal.
- Write the order of nodes visited in a pre-order traversal after removal.
Solution
```
graph TB;
A((4))
B((3))
C((7))
D((2))

A-->B
A-->C
B-->D
B~~~X:::hidden

classDef hidden display: none;
```
- Pre-order traversal: 4, 3, 2, 7

BST Removal Summary

Let's work on developing your intuition for removals! Here's how you can think about it:

If the node has no children (a leaf node), just remove it.
If the node has one child, remove the node and replace it with its child (either the left or the right).
If the node has two children:
1. Find the largest value in the left subtree (or smallest value in the right subtree). This will be a leaf node.
  - You are looking for this node's "in-order predecessor". The in-order predecessor is the largest value in the left subtree.
  - We are using the in-order predecessor, but other implementations may use the in-order successor. The choice is arbitrary, but it is important to be consistent.
    - The in-order successor is the smallest value in the right subtree.
2. Replace this node's value with the value of the in-order predecessor (or successor).
  - This is important because we need to maintain the BST property. The largest value in the left subtree is guaranteed to be less than the node's value, and the smallest value in the right subtree is guaranteed to be greater than the node's value.
3. Delete the node that contains the in-order predecessor (or successor).
  - This is now easy to do, because the in-order predecessor (or successor) is a leaf node. So we can just remove it.

Part 3: Analyzing Performance of BSTs

(15 min)

Now, think about performance. Assume the tree is balanced. Think about how many nodes you would have to visit to find a value:
- What is the worst-case time complexity of searching for a value in a balanced BST?
Hint

Draw a balanced or complete tree. How many nodes would you have to visit to find a value?

Note that you only check one node per level of the tree. How many levels are in a balanced tree? See this article.

Solution

The worst-case time complexity is \(\Theta(h)\), where h is the height of the tree. For a balanced tree, the height is \(\Theta(log\ n)\), where n is the number of nodes in the tree. So the worst-case time complexity is also \(\Theta(log\ n)\).
What if the tree is unbalanced? Think about how many nodes you would have to visit to find a value:
- What is the worst-case time complexity of searching for a value in an unbalanced BST?
Hint

Draw the worst possible tree.

Solution

The worst-case time complexity is \(\Theta(n)\), where n is the number of nodes in the tree. Why? Because the tree is essentially a linked list, and we would have to visit every node to find the value.

Here's an example of a perfect BST with 15 nodes:

graph TB;
    A(( ))
    B(( ))
    C(( ))
    D(( ))
    E(( ))
    F(( ))
    G(( ))
    H(( ))
    I(( ))
    J(( ))
    K(( ))
    L(( ))
    M(( ))
    N(( ))
    O(( ))

    A-->B
    A-->C
    B-->D
    B-->E
    C-->F
    C-->G
    D-->H
    D-->I
    E-->J
    E-->K
    F-->L
    F-->M
    G-->N
    G-->O

Let's generalize. For a perfect BST with n nodes, let's determine the average number of nodes visited to find a value:
- Assume that each value is equally likely to be searched for.
- Start by thinking about how many levels there are in the tree, and how many nodes are at each level.
- In terms of n, how many levels are in a perfect BST?
- Assume L stands for a given level of the tree. The root is at L=0.
  
  How many nodes are at a given level L?
- For a node at level L, how many nodes would you have to visit to get to that node? State this in terms of L.
  
  How many nodes would you have to visit to find a value at level L?
- We will discuss average-case analysis together with these observations.

Takeaway

Binary search trees are a powerful data structure that allow for efficient searching.

The worst-case time complexity of searching in a balanced BST is \(\Theta(log\ n)\).
The worst-case time complexity of searching in an unbalanced BST is \(\Theta(n)\).

Thus, it is important to keep a BST balanced to ensure efficient searching.

Submission

For these activities, you will typically submit a PDF report to Canvas. First, click the "Export as PDF" button below.

Then, submit the PDF to Canvas. Everyone must submit their own copy to receive credit.