Unit 9 — Data Structures

Slide 1 of 62

The problem: The Library Robot

The school library has a new helper robot, and it keeps everything it handles in careful order. Three jobs keep it busy, and each one hides a puzzle.

1. The returns cart. Returned books go on a cart, each one on top of the others, and the robot always shelves the top book first. At the help desk, students wait in a line, and the robot always helps whoever has waited longest.
On Monday morning books M, A and P are returned, in that order. The robot shelves one book. Then book S is returned, and the robot shelves two more books. Which book is shelved third?

The same morning, students M, A and P join the line, one is helped, S joins, and two more are helped. Who is helped third?
2. The letter tree. To find things fast, the robot files the letters of a word in a tree. The first letter goes at the top. Each later letter starts at the top and moves down: left if it comes before the letter it meets in the alphabet (or is the same letter), right if it comes after, until it finds an empty place.

The robot files the letters of SHELF. How many steps down from the top does each letter end up, and what is the total?
3. The urgent pile. Requests with priority numbers 30, 12, 25, 7 and 18 arrive, and the robot must always be able to grab the smallest number at once, without sorting the whole pile each time. How does it keep them, and what happens when the smallest one is taken away?
By the end of Lesson 1 you can answer the first puzzle, by the end of Lesson 2 the second, and by the end of Lesson 3 the third. These are exactly the data structures of ACSL's Contest 3: stacks, queues, binary search trees and heaps.
- Trace PUSH and POP on a stack (last in, first out) and a queue (first in, first out).
- Build a binary search tree by ACSL's rules, and read its depths, height, leaves and internal path length.
- Intermediate and above: find external nodes and traversals, and build min-heaps and max-heaps.
- Senior: remove the root of a heap and delete a node from a binary search tree.
- Write each structure in Python with lists.
Lesson 1 — Stacks and queues

Division: Junior and above.

Two ways to keep a pile

A stack works like the returns cart: the last item put on is the first one taken off. This is called LIFO, "last in, first out".

A queue works like the line at the help desk: the first item put in is the first one taken out. This is called FIFO, "first in, first out".

ACSL uses the same two commands for both:

Command	On a stack	On a queue
`PUSH(x)`	puts `x` on the top	puts `x` at the back of the line
`X = POP()`	takes the top item off, and stores it in `X`	takes the item at the front off, and stores it in `X`

If the stack or queue is empty, POP() has nothing to take, and the value it gives is NIL. POP() on its own line, with no X =, still takes the item off: the value is just not kept.
Names in a script. A one-letter name that was given a value by = POP() (such as X) stands for that value. Any other letter or word inside PUSH( ) is pushed as itself. ACSL's own page writes pushed letters in quotes, PUSH("A"); this book leaves the quotes off, so PUSH(A) pushes the letter A.
Tracing a stack

Write the stack bottom to top, left to right, after every command. Here is the returns cart from the problem:

Command Stack after (bottom to top) Value

PUSH(M) M

PUSH(A) M A

PUSH(P) M A P

X = POP() M A X = P

PUSH(S) M A S

Y = POP() M A Y = S

Z = POP() M Z = A

The third book shelved is A.
Tracing a queue

Write the queue front to back, left to right. New items join on the right, and POP() takes from the left. Here is the help-desk line:

Command Queue after (front to back) Value

PUSH(M) M

PUSH(A) M A

PUSH(P) M A P

X = POP() A P X = M

PUSH(S) A P S

Y = POP() P S Y = A

Z = POP() S Z = P

The third student helped is P. The same commands gave a different answer, because only the rule for POP changed.

Watch out: one more POP() on either structure would empty it, and a POP() after that gives NIL.
Arithmetic on popped values

Division: Intermediate and above.

Intermediate and Senior questions do sums with the popped values and push the results back. This is the sample from ACSL's own page:

Command Stack after Value

PUSH(3) 3

PUSH(6) 3 6

PUSH(8) 3 6 8

Y = POP() 3 6 Y = 8

X = POP() 3 X = 6

PUSH(X - Y) 3 -2 6 − 8 = −2

Z = POP() 3 Z = −2

So Z = −2. Work out the sum when it is pushed, using the values the names have at that moment, and push only the answer.
A stack in Python

Unit 4 kept a stack as a Python list stack together with a count top, and never shrank the list:
- push: if top equals len(stack), append; otherwise write over stack[top]. Then add 1 to top.
- pop: if top is 0 the stack is empty (NIL); otherwise take 1 from top, and the value is stack[top].
This program runs a script of commands, each one either "PUSH x" or "POP", and prints every popped value.

Command	Stack after (bottom to top)	Value
`PUSH(M)`	M
`PUSH(A)`	M A
`PUSH(P)`	M A P
`X = POP()`	M A	X = P
`PUSH(S)`	M A S
`Y = POP()`	M A	Y = S
`Z = POP()`	M	Z = A

Command	Queue after (front to back)	Value
`PUSH(M)`	M
`PUSH(A)`	M A
`PUSH(P)`	M A P
`X = POP()`	A P	X = M
`PUSH(S)`	A P S
`Y = POP()`	P S	Y = A
`Z = POP()`	S	Z = P

Command	Stack after	Value
`PUSH(3)`	3
`PUSH(6)`	3 6
`PUSH(8)`	3 6 8
`Y = POP()`	3 6	Y = 8
`X = POP()`	3	X = 6
`PUSH(X - Y)`	3 -2	6 − 8 = −2
`Z = POP()`	3	Z = −2

script = ["PUSH 2", "PUSH 9", "PUSH 5", "POP", "PUSH 3", "POP", "POP", "POP", "POP"]

stack = []
top = 0
for command in script:
    parts = command.split()
    if parts[0] == "PUSH":
        if top == len(stack):
            stack.append(parts[1])
        else:
            stack[top] = parts[1]
        top = top + 1
    elif top == 0:
        print("NIL")
    else:
        top = top - 1
        print(stack[top])

Output

5
3
9
2
NIL

The pops print 5, 3, 9, 2 and then NIL: the fifth POP found the stack empty.

A queue in Python

A queue is a list plus a head index: the position of the item at the front.
- push: append the value to the end of the list.
- pop: if head equals len(queue), the queue is empty (NIL); otherwise the value is queue[head], and head goes up by 1.
The items before head have already left the line; the program just never looks at them again.

script = ["PUSH R", "PUSH U", "PUSH N", "POP", "PUSH S", "POP", "POP", "POP", "POP"]

queue = []
head = 0
for command in script:
    parts = command.split()
    if parts[0] == "PUSH":
        queue.append(parts[1])
    elif head == len(queue):
        print("NIL")
    else:
        print(queue[head])
        head = head + 1

Output

R
U
N
S
NIL

The letters come out R, U, N, S in the order they went in, and then NIL. Change head == len(queue) to head == 0 and run it again: the empty test is the part people get wrong.
Put it together: this program reads STACK or QUEUE on the first line, and a script on the second line, such as PUSH 2 PUSH 9 POP. After every command it prints the command and the contents (bottom to top for a stack, front to back for a queue), just like the tables above. It is saved as assets/l1.py.

Try it

kind = input()
tokens = input().split()

items = []
top = 0
head = 0
i = 0
while i < len(tokens):
    if tokens[i] == "PUSH":
        value = tokens[i + 1]
        if kind == "STACK":
            if top == len(items):
                items.append(value)
            else:
                items[top] = value
            top = top + 1
        else:
            items.append(value)
        line = "PUSH " + value + " :"
        i = i + 2
    else:
        if kind == "STACK":
            if top == 0:
                popped = "NIL"
            else:
                top = top - 1
                popped = items[top]
        else:
            if head == len(items):
                popped = "NIL"
            else:
                popped = items[head]
                head = head + 1
        line = "POP -> " + popped + " :"
        i = i + 1
    if kind == "STACK":
        for k in range(top):
            line = line + " " + items[k]
    else:
        for k in range(head, len(items)):
            line = line + " " + items[k]
    print(line)

Run it from this unit's folder:
```
python assets/l1.py < assets/l1/1.in
```
The input is a stack script whose last line is POP -> NIL :, a pop from an empty stack. assets/l1/2.in runs a queue, and assets/l1/3.in starts with a POP on an empty stack. Trace each one by hand first, then use the program to check your tables.
Lesson 2 — Binary search trees

Division: Junior and above.
Building the tree

A binary search tree (BST) stores keys (letters or numbers) in nodes. Each node has at most two children: a left child and a right child. The top node is the root.

To build a BST, insert the keys one at a time, in the order given:
1. The first key becomes the root.
2. Each later key starts at the root. If it is less than or equal to the key there, go left; if it is greater, go right.
1. Keep going down until the place you want is empty, and put the key there.
The "or equal" is ACSL's rule for duplicates: a key equal to one already in the tree goes to the left, as if it were smaller. Letters compare in alphabetical order, so A is less than B.

Example 1. The puzzle's word, SHELF.
- S is the root.
- H comes before S: left of S.
- E: before S, go left; before H, go left. It goes left of H.

L: before S, go left; after H, go right. It goes right of H.
F: left at S, left at H, right at E. It goes right of E.

Example 2. ACSL's sample word, PROGRAM. The second R meets the first R, is equal, and goes to its left.

Depth, height, leaves and internal path length
- The depth of a node is the number of steps down from the root. The root has depth 0.
- The height of the tree is the greatest depth of any node.
- A leaf is a node with no children.
- The internal path length is the sum of the depths of all the nodes.
Example 3. In SHELF: S has depth 0, H depth 1, E and L depth 2, and F depth 3. The internal path length is 0 + 1 + 2 + 2 + 3 = 8, which answers the second puzzle. The height is 3, and the leaves are F and L.
Example 4. In PROGRAM (ACSL's sample): P is at depth 0; O and R at depth 1; G and the second R at depth 2; A and M at depth 3. The internal path length is 0 + 2 × 1 + 2 × 2 + 2 × 3 = 12. The leaves are A, M and the second R.

Watch out: a duplicate is a separate node with its own depth. PROGRAM has seven letters, so its tree has seven nodes.
A BST in Python

This book keeps a BST in three parallel lists: key[i] is the key of node i, and left[i] and right[i] are the numbers of its children, with -1 for "no child". Nodes are numbered in the order they are inserted, so node 0 is the root.

insert adds one key and walks down from the root with a while loop, exactly as in the rules above. It returns the depth where the key landed.

def insert(key, left, right, letter):
    key.append(letter)
    left.append(-1)
    right.append(-1)
    new = len(key) - 1
    depth = 0
    node = 0
    placed = new == 0
    while not placed:
        depth = depth + 1
        if letter <= key[node]:
            if left[node] == -1:
                left[node] = new
                placed = True
            else:
                node = left[node]
        else:
            if right[node] == -1:
                right[node] = new
                placed = True
            else:
                node = right[node]
    return depth


key = []
left = []
right = []
total = 0
for letter in "PROGRAM":
    depth = insert(key, left, right, letter)
    print(letter, depth)
    total = total + depth
print("internal path length:", total)
print("key:  ", key)
print("left: ", left)
print("right:", right)

Output

P 0
R 1
O 1
G 2
R 2
A 3
M 3
internal path length: 12
key:   ['P', 'R', 'O', 'G', 'R', 'A', 'M']
left:  [2, 4, 3, 5, -1, -1, -1]
right: [1, -1, -1, 6, -1, -1, -1]

The depths match Example 4, and total is 12. Look at the lists: node 0 is P, and left[0] is 2 and right[0] is 1, because O (node 2) is the left child of P and R (node 1) is its right child. placed = new == 0 means the very first key is already in place: it is the root, at depth 0.
External nodes and external path length

Division: Intermediate and above.

Every empty place where a new node could be attached is an external node. A leaf has two of them, and a node with one child has one. The depth of an external node is one more than the depth of the node it hangs from. The external path length is the sum of the depths of all the external nodes.

Example 5. In SHELF, the external nodes hang from:

Node (depth) Empty places Their depth

S (0) right 1

H (1) none

E (2) left 3

L (2) left, right 3, 3

F (3) left, right 4, 4
There are 6 external nodes, and the external path length is 1 + 3 + 3 + 3 + 4 + 4 = 18.

Two facts make a good check:
- a tree with n nodes always has n + 1 external nodes;
- the external path length is always the internal path length plus 2n. For SHELF, 8 + 2 × 5 = 18.

Node (depth)	Empty places	Their depth
`S` (0)	right	1
`H` (1)	none
`E` (2)	left	3
`L` (2)	left, right	3, 3
`F` (3)	left, right	4, 4

Traversals

A traversal visits every node once. Each of the three orders is a rule applied at every node, starting from the root:

Traversal	Order at every node
inorder	the left subtree, then the node, then the right subtree
preorder	the node, then the left subtree, then the right subtree
postorder	the left subtree, then the right subtree, then the node

Example 6. ACSL's word AMERICAN. The second A equals the root and goes left.

inorder: AACEIMNR
preorder: AAMECIRN
postorder: ACIENRMA

The inorder traversal of a BST always lists the keys in sorted order, which is a quick check on your tree. For preorder, a good habit is to write the root first and then finish the whole left side before you touch the right.
Traversals in Python

Each traversal is a recursive function (Unit 2): the traversal of a tree is built from the traversals of its two subtrees. An empty subtree (-1) gives the empty string.

def inorder(node, key, left, right):
    if node == -1:
        return ""
    return inorder(left[node], key, left, right) + key[node] + inorder(right[node], key, left, right)


def preorder(node, key, left, right):
    if node == -1:
        return ""
    return key[node] + preorder(left[node], key, left, right) + preorder(right[node], key, left, right)


key = []
left = []
right = []
for letter in "AMERICAN":
    insert(key, left, right, letter)
print(inorder(0, key, left, right))
print(preorder(0, key, left, right))

Output

AACEIMNR
AAMECIRN

The two lines match Example 6. The only difference between the two functions is where key[node] sits in the return line. Write postorder yourself by moving it to the end, and check that it prints ACIENRMA.

Put it together: this program reads a word, builds its BST, and prints the letters at each depth, left to right, and then the internal path length. It fills one text row per depth with a recursive walk in inorder, which visits each row's letters from left to right. It is saved as assets/l2.py.

Try it

def insert(key, left, right, letter):
    key.append(letter)
    left.append(-1)
    right.append(-1)
    new = len(key) - 1
    depth = 0
    node = 0
    placed = new == 0
    while not placed:
        depth = depth + 1
        if letter <= key[node]:
            if left[node] == -1:
                left[node] = new
                placed = True
            else:
                node = left[node]
        else:
            if right[node] == -1:
                right[node] = new
                placed = True
            else:
                node = right[node]
    return depth


def fill_rows(node, depth, key, left, right, rows):
    if node == -1:
        return
    if depth == len(rows):
        rows.append("")
    fill_rows(left[node], depth + 1, key, left, right, rows)
    rows[depth] = rows[depth] + key[node]
    fill_rows(right[node], depth + 1, key, left, right, rows)


word = input()
key = []
left = []
right = []
total = 0
for letter in word:
    total = total + insert(key, left, right, letter)

rows = []
fill_rows(0, 0, key, left, right, rows)
for depth in range(len(rows)):
    print("depth " + str(depth) + ": " + rows[depth])
print("internal path length: " + str(total))

Run it from this unit's folder:
```
python assets/l2.py < assets/l2/1.in
```
The input PROGRAM prints four rows, depth 0: P down to depth 3: AM, then internal path length: 12. assets/l2/3.in holds BOOKSHELF, with a duplicate O; draw its tree by hand first.
Lesson 3 — Heaps, and taking things out

Division: Intermediate and above.
Priority queues and min-heaps

The robot's urgent pile is a priority queue: whatever else happens, the smallest item must always be ready to take. ACSL keeps a priority queue as a heap, a tree where each node has at most two children and:
- every node is less than or equal to both of its children (so the root is the smallest item), and
- the tree has no gaps: every row is full except perhaps the bottom one, which is filled from the left.
This is a min-heap. Unlike a BST, a heap says nothing about left against right: only parent against child.

Inserting. Put the new item in the next free place (the bottom row, as far left as possible). Then, while it is smaller than its parent, swap it with its parent.

Example 1. The urgent pile: 30, 12, 25, 7, 18.

Insert What happens Rows after

30 the root 30

12 12 < 30, swap 12 / 30

25 25 > 12, stays 12 / 30 25

7 7 < 30, swap; 7 < 12, swap 7 / 12 25 / 30

18 18 > 12, stays 7 / 12 25 / 30 18
```
        7
      /   \
    12     25
   /  \
  30   18
```
Example 2. ACSL's sample: the letters of PROGRAMMING, inserted in order, give a min-heap whose rows are A, GG, MIPM and RORN. The bottom row, left to right, is RORN.

Positions. Number the places row by row, left to right, with the root at position 1. Then the children of position i are at positions 2i and 2i + 1, and the parent of position i is at i // 2. In Example 1, 30 is at position 4 and 18 at position 5.
Max-heaps. A max-heap turns every comparison round: each node is greater than or equal to its children, so the root is the largest. When inserting, swap while the new item is larger than its parent. A question always says which kind it wants; if it just says "heap", it means a min-heap.
A heap in Python

A heap fits neatly in a list: position i of the heap is heap[i]. Slot 0 is left unused (it holds ""), so the children of heap[i] really are heap[2 * i] and heap[2 * i + 1]. Inserting appends, then swaps upward while the parent is larger. The swap uses a tuple, a, b = b, a.

Insert	What happens	Rows after
30	the root	30
12	12 < 30, swap	12 / 30
25	25 > 12, stays	12 / 30 25
7	7 < 30, swap; 7 < 12, swap	7 / 12 25 / 30
18	18 > 12, stays	7 / 12 25 / 30 18

heap = [""]
for letter in "PROGRAMMING":
    heap.append(letter)
    i = len(heap) - 1
    while i > 1 and heap[i // 2] > heap[i]:
        heap[i // 2], heap[i] = heap[i], heap[i // 2]
        i = i // 2
print(heap)

start = 1
while start < len(heap):
    row = ""
    for i in range(start, min(2 * start, len(heap))):
        row = row + heap[i]
    print(row)
    start = 2 * start

Output

['', 'A', 'G', 'G', 'M', 'I', 'P', 'M', 'R', 'O', 'R', 'N']
A
GG
MIPM
RORN

The rows come out A, GG, MIPM, RORN, matching Example 2. Row by row, the positions run 1, then 2–3, then 4–7, then 8–15: each row starts at double the start of the one above, and the last row stops at the end of the list. For a max-heap, change heap[i // 2] > heap[i] to heap[i // 2] < heap[i].

Put it together: this program reads a word and prints the rows of its min-heap. It is saved as assets/l3.py.

Try it

word = input()

heap = [""]
for letter in word:
    heap.append(letter)
    i = len(heap) - 1
    while i > 1 and heap[i // 2] > heap[i]:
        heap[i // 2], heap[i] = heap[i], heap[i // 2]
        i = i // 2

start = 1
while start < len(heap):
    row = ""
    for i in range(start, min(2 * start, len(heap))):
        row = row + heap[i]
    print(row)
    start = 2 * start

Run it from this unit's folder:
```
python assets/l3.py < assets/l3/1.in
```
The input PROGRAMMING prints the four rows of Example 2. assets/l3/3.in holds EDCBA: every new letter is the smallest so far, so every insert swaps all the way to the root.
Removing the root of a heap

Division: Senior and above.

Taking the smallest item out of a min-heap is ACSL's heap deletion:
1. Take out the root.
2. Move the last item (the bottom row's right-most item) into the root's place.
3. While it is larger than its smaller child, swap it with that smaller child.
In a max-heap, swap with the larger child while the item is smaller than it. If the two children are equal, this book swaps with the left one; ACSL's page does not say, and the exercises never depend on it.
Example 3. Take 7 out of the urgent pile, 7 / 12 25 / 30 18.
- The last item, 18, moves to the root: 18 / 12 25 / 30.
- Its children are 12 and 25; the smaller is 12, and 18 > 12, so swap: 12 / 18 25 / 30.
- Now 18 has one child, 30, and 18 < 30, so it stops.
The new rows are 12, 18 25, 30, and the robot's next urgent request is 12. That answers the third puzzle.
In Python, the list never shrinks: keep a count size of the items still in the heap, and only look at positions 1 to size.

heap = [0, 7, 12, 25, 30, 18]
size = 5

print("taken out:", heap[1])
heap[1] = heap[size]
size = size - 1
i = 1
done = False
while not done and 2 * i <= size:
    child = 2 * i
    if child + 1 <= size and heap[child + 1] < heap[child]:
        child = child + 1
    if heap[child] < heap[i]:
        heap[i], heap[child] = heap[child], heap[i]
        i = child
    else:
        done = True

for position in range(1, size + 1):
    print(position, heap[position])

Output

taken out: 7
1 12
2 18
3 25
4 30

Positions 1 to 4 hold 12, 18, 25 and 30, as in Example 3. The line if child + 1 <= size and ... makes sure a right child really exists before comparing with it.
Deleting from a BST

Division: Senior and above.

ACSL deletes a node p from a BST like this, where f is the parent of p:
- No children: just remove p.
- One child: that child (with everything below it) takes p's place as f's child.
- Two children, a left child l and a right subtree r: l (with everything below it) takes p's place, and r is attached to the l tree where BST order puts it, as the right child of the right-most node of the l tree. To find that node, start at l and keep going right until there is no right child.
If p is the root, the node that takes its place becomes the new root. Items in this book never delete a letter that appears more than once, since ACSL gives no rule for which copy goes.

Example 4. The word MOUNTAINS gives this tree (the second N went left of the first):
```
          M
        /   \
       A     O
        \   / \
         I N   U
          /   /
         N   T
            /
           S
```
- Delete I: it is a leaf, so it just goes.
- Delete T: it has one child, S, which takes its place as the left child of U.
- Delete the root M: its left child l is A, and its right subtree r starts at O. A becomes the root. The right-most node of A's tree is found by going right from A: A, then I, which has no right child. So the whole O subtree becomes the right child of I:
```
      A
       \
        I
         \
          O
         / \
        N   U
       /   /
      N   T
         /
        S
```
The preorder traversal of the new tree is AIONNUTS. A good check: the new tree's inorder is still the sorted letters, minus the deleted one.
- POP on an empty stack or queue gives NIL.
- In an ACSL binary search tree, a duplicate goes left, and the root has depth 0.
- Intermediate and above: inorder, preorder and postorder differ only in when each node is visited: between, before or after its subtrees.
- Intermediate and above: a new heap item goes in the next free place, then swaps with its parent while it is smaller (in a min-heap).
- In Python, a stack needs a top count, a queue a head index, and a binary search tree three parallel lists: key, left and right.
You can now trace stacks, queues, trees and heaps the way ACSL asks.

Unit 9 — Data Structures

The problem: The Library Robot

Lesson 1 — Stacks and queues

Two ways to keep a pile

Tracing a stack

Tracing a queue

Arithmetic on popped values

A stack in Python

A queue in Python

Lesson 2 — Binary search trees

Building the tree

Depth, height, leaves and internal path length

A BST in Python

External nodes and external path length

Traversals

Traversals in Python

Lesson 3 — Heaps, and taking things out

Priority queues and min-heaps

A heap in Python

Removing the root of a heap

Deleting from a BST