COSC122 (2020) Lab 7.1

Trees

Goals

This lab will give you practice with trees; in this lab you will:

• Warm up by traversing parse trees.

• Check that you understand how to insert in to a binary search tree.

• Implement methods for traversing a binary search tree.

• Implement methods for deleting from a binary search tree.

This lab covers the material in Sections 6.1–6.5 and 6.7 of the textbook or check out the online textbook

chapter 1

.

Parse Trees

Mathematical expressions can be stored in trees and traversing such trees in different orders will produce different versions of the expressions, eg, an in-order traversal will produce an equation in infix

notation and a post-order traversal will produce the post-fix notation version of the equation.

> Complete the Parse Trees questions in Lab Quiz 7.1.

∗

+

3 8

−

10 8

Figure 1: Example of a parse tree

Binary Search Trees

The provided trees module provides a Node class for representing nodes in a binary search tree, and

an incomplete BinarySearchTree class. A few doctests for the methods in BinarySearchTree have

also been provided.

Most of the methods in BinarySearchTree have two versions: a public method that sets up a call

to a private method. For example, insert calls _insert. The methods have been designed this way

so that the private methods can work recursively on any subtree; this keeps their implementations and

logic simple.

1Online Text: https://runestone.academy/runestone/static/pythonds/Trees/toctree.html.

Insertion

Examine the insert and _insert methods and ensure you understand how they traverse the tree and

find the correct location to place the item to be inserted.

> Complete the Building BSTs questions in Lab Quiz 7.1.

Traversing

13

15

18

16

13

9

10

11

8

Figure 2: Example for Binary Search Tree Traversal Q’s

Inorder traversal of a binary search tree produces a sorted list of items stored in the tree–no further

comparisons or swaps need to take place.

The in_order_items method should return a sorted list of all items in the tree. It starts this

process by creating an empty list to store the items and calling _in_order_items, which should

recursively walk through the tree.

1. Implement _in_order_items with the following algorithm:

• If the subtree is None, then stop. (This is the base case.)

• Recurse into the left subtree.

• Add the subtree node’s value to out_list).

• Recurse into the right subtree.

2. Test your implementation with the provided doctests.

3. Build the tree in Figure 2 and produce an in-order traversal.

4. Write a method for pre-order traversal.

5. Now traverse the same tree (Figure 2) using pre-order traversal.

6. Repeat the steps above for post-order traversal.

> Complete the Traversing BSTs questions in Lab Quiz 7.1.

2

Deleting

The last method you need to complete is _remove to delete a value from the tree.

Removing values from a binary tree is performed in two steps:

1. Find the item to remove.

2. Remove the item.

Finding the item follows the algorithm implemented by _contains; however, when the item is found,

there are three cases that need to be handled (illustrated in Figure 3):

• If the item is a leaf node (it has no children), then its parent’s reference to it is set to None—

removing all references to it from the tree.

• If the item only has one child, then the reference to the item from its parent is set to the item’s

child—replacing the item with its child.

• However, if the node has two children, then a suitable replacement needs to be found in its subtree. Remember that a parent must be larger than all of the nodes in the left subtree, and smaller

than all of the nodes in the right subtree. An appropriate item can be found by promoting either the in-order predecessor (the largest item from the left subtree) or the in-order successor (the

smallest item from the right subtree) to the position of the item being deleted.

5

3 9

Delete branch

X

(a)

5

3 9

7

Promote Child

X

(b)

5

3 9

7 11

10

Promote In-Order

Successor

X

(c)

Figure 3: Deleting the ‘9’ node from a tree with (a) no children, (b) one child, and (c) two children.

Understanding how to find the in-order-successor is an important part of the deletion process. The

questions in the BST deletion helpers section of Lab quiz 7.1 are designed to check your understanding

so make sure you do question 6 before continuing.

> Complete the questions in the BST deletion helpers section of Lab Quiz 7.1

3

Implementing the Remove operation

Your task here is to get the _remove functionality working. To do this you will won’t actually need to add

any code to the _remove method itself but you will want to understand what it, and it’s helpers is doing.

The code you need to write will be in the _pop_min_recursive method.

The _remove method takes in the value to remove, and the subtree to remove it from; the method

returns a replacement node for the subtree (which may be subtree itself, if it doesn’t need replacing).

Code for locating the item to be deleted has been provided, you only need to complete the marked

section for actually removing the item from the tree.

As part of this, you will need to understand the _pop_in_order_successor and its helper function

_pop_min_recursive. You will then need to implement the _pop_min_recursive method to find the

value of the smallest item in a subtree (which will be the right node of the item to be deleted) and

return the value. As a side effect, _pop_min_recursive should remove the smallest value node from

the given subtree (which will be the in-ordersuccessor node of the node being deleted). So, the node

that contains the value that is being removed from the tree actually stays in the tree but this node now

contains the value of the in order successor (and the node that had the in order successor value will be

the node that is removed). If you are confused, think about the distinction between a node and a node’s

value.

Test your implementation with the provided doctests.

> Complete the questions in the Testing Deletion section of Lab Quiz 7.1.

4

Sale!