Practice: Ordering Exam Scores as They Arrive

Scores arrive one by one; insert them, then delete one and list the rest in order.

Exam scores that arrive one at a time can be kept in order by inserting each into a binary search tree as it comes in. This card covers that as an exercise in building a tree by hand, deleting a key with two children, and reading the sorted order back out, with an answer to check yours against.

Seven scores arrive in this order: 72, 85, 64, 90, 78, 91, 58. No two are equal.

Insert the scores into an empty binary search tree in the order they arrive, and draw the tree.
Give its height in edges, and say how many comparisons a search for 91 makes.
The 85 was entered in error. Delete it using the in-order successor, and draw the tree again.
List the remaining scores in sorted order, and name the traversal that produces them.
Say which arrival order of these seven scores would give the tallest possible tree, and what its height would be.

An answer: both trees, the height, and the sorted scores

72 arrives first and stays the root. Each later score descends from it to the first empty link: 85 right of 72, 64 left of it, 90 right of 85, 78 left of 85, 91 right of 90, and 58 left of 64. The longest path, from 72 to 91, has three edges, so the height is 3, and a search for 91 compares 72, 85, 90 and 91: four comparisons.

The scores inserted in the order they arrived: height 3

72, root, arrived first
- 64
  - 58
  - null, empty right link
- 85, to be deleted: two children
  - 78
  - 90, successor of 85
    - null, empty left link
    - 91

85 has two children, so its key is replaced by its successor, the leftmost node of its right subtree. From 85 go right to 90; 90 has no left child, so 90 is the successor. 90 is copied into the node that held 85, and the old 90, which has one child, 91, is removed by letting 91 take its place. The tree is one level shorter.

The tree after deleting 85: height 2

72, root
- 64
  - 58
  - null, empty right link
- 90, took the place of 85
  - 78
  - 91

An in-order traversal lists the six remaining scores from lowest to highest: 58 64 72 78 90 91. The listing builds the tree, deletes 85 and prints each stage:

exam_scores.pypy

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node


def height(node):
    return -1 if node is None else 1 + max(height(node.left), height(node.right))


def shape(node):
    if node is None:
        return "-"
    if node.left is None and node.right is None:
        return str(node.key)
    return f"{node.key}({shape(node.left)}, {shape(node.right)})"


def in_order(node, keys):
    if node is not None:
        in_order(node.left, keys)
        keys.append(node.key)
        in_order(node.right, keys)
    return keys


def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    elif node.left is None:
        return node.right
    elif node.right is None:
        return node.left
    else:
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        print(f"delete {key}: two children, in-order successor {successor.key}")
        node.key = successor.key
        node.right = delete(node.right, successor.key)
    return node


root = None
for score in (72, 85, 64, 90, 78, 91, 58):
    root = insert(root, score)
    print(f"insert {score}: {shape(root)}")
print("height:", height(root))
print("in-order:", *in_order(root, []))
root = delete(root, 85)
print("after deleting 85:", shape(root))
print("height:", height(root))
print("in-order:", *in_order(root, []))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

insert 72: 72
insert 85: 72(-, 85)
insert 64: 72(64, 85)
insert 90: 72(64, 85(-, 90))
insert 78: 72(64, 85(78, 90))
insert 91: 72(64, 85(78, 90(-, 91)))
insert 58: 72(64(58, -), 85(78, 90(-, 91)))
height: 3
in-order: 58 64 72 78 85 90 91
delete 85: two children, in-order successor 90
after deleting 85: 72(64(58, -), 90(78, 91))
height: 2
in-order: 58 64 72 78 90 91

The tallest tree comes from sorted arrival, lowest first or highest first: every score becomes the only child of the one before, a chain of height 6, one less than the number of scores. Other orders build a chain too: any order in which each score is the lowest or the highest of the scores still to come, such as 58, 91, 64, 90, 72, 85, 78. A run gave all three of these orders a height of 6.

← → move through sections and cards