Data Structures

ACSL tests three data structures: stacks, queues, and binary search trees. You won’t write code to implement them - you’ll trace operations by hand. The key is knowing exactly what each operation does.

Stacks (LIFO)

A stack is Last In, First Out - like a stack of plates. You can only add or remove from the top.

Operations:

PUSH(x) - add x to the top
POP() - remove and return the top item

Example: What is Z after these operations?

PUSH(3)
PUSH(6)
PUSH(8)
Y = POP()
X = POP()
PUSH(X - Y)
Z = POP()

Trace the stack (top is rightmost):

Operation	Stack	Notes
$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$

Answer: $Z = - 2$

Common trap: POP returns the most recently pushed item. Students sometimes read the stack in the wrong order.

Try it: trace a stack

Step through this stack program and watch how items enter and leave from the top.

Code

1PUSH(3)2PUSH(6)3PUSH(8)4Y = POP()5X = POP()6PUSH(X - Y)7Z = POP()

Variables

Name	Value
Stack	[3]

Step 1 of 7

Queues (FIFO)

A queue is First In, First Out - like a line at a store. Items are added to the back and removed from the front.

Operations:

ENQUEUE(x) or PUSH(x) - add x to the back
DEQUEUE() or POP() - remove and return the front item

Example:

ENQUEUE(5)
ENQUEUE(3)
ENQUEUE(8)
A = DEQUEUE()
ENQUEUE(1)
B = DEQUEUE()

Operation	Queue (front to back)	Notes
$ENQUEUE (5)$	$[5]$
$ENQUEUE (3)$	$[5, 3]$
$ENQUEUE (8)$	$[5, 3, 8]$
$A = DEQUEUE ()$	$[3, 8]$	$A = 5$
$ENQUEUE (1)$	$[3, 8, 1]$
$B = DEQUEUE ()$	$[8, 1]$	$B = 3$

Stack vs Queue confusion: If ACSL says “stack,” items leave from the same end they entered. If “queue,” items leave from the opposite end.

Binary search trees (BSTs)

A BST is a tree where:

Each node’s left subtree contains only values less than the node
Each node’s right subtree contains only values greater than the node

Building a BST

Insert values one at a time. The first value becomes the root. Each subsequent value goes left if smaller, right if larger.

Example: Build a BST from the letters P, R, O, G, R, A, M (using alphabetical order, skip duplicates)

     P
    /    O   R
  /
 G
/ A   M

Step by step:

P is the root
R goes right of P (R comes after P alphabetically)
O goes left of P (O comes before P)
G goes left of O (G comes before O)
R is a duplicate, skip
A goes left of G (A comes before G)
M goes right of G (M comes after G, before O)

Tree traversals

ACSL tests three traversal orders. Use these mnemonics:

Inorder (Left, Root, Right) - visits nodes in sorted order for a BST

A, G, M, O, P, R

Preorder (Root, Left, Right) - root first, then left subtree, then right

P, O, G, A, M, R

Postorder (Left, Right, Root) - root last

A, M, G, O, R, P

Memory trick: The name tells you where the Root goes:

Preorder = root first
Inorder = root in the middle
Postorder = root last

And Left always comes before Right.

Internal path length

The internal path length is the sum of the depths of all nodes (root has depth 0).

For our BST:

     P (depth 0)
    /    O   R (depth 1)
  /
 G (depth 2)
/ A   M (depth 3)

IPL $= 0 + 1 + 1 + 2 + 3 + 3 =$ 10

External path length

The external path length is the sum of depths of every “null” child slot - every place where a node could be inserted. A node with no left child contributes one external node on its left, and same for the right.

For our BST, the null slots are at:

A: left and right children missing (depth 4 each)
M: left and right children missing (depth 4 each)
O: right child missing (depth 2)
R: left and right children missing (depth 2 each)

EPL $= 4 + 4 + 4 + 4 + 2 + 2 + 2 =$ 22

Shortcut: For any binary tree, $EPL = IPL + 2 n$ , where $n$ is the number of nodes. Here: $10 + 2 (6) = 22$ . This saves time on the contest.

Deleting from a BST

When deleting a node:

Leaf node: just remove it
One child: replace the node with its child
Two children: the left child takes the deleted node’s position, and the entire right subtree is attached to the rightmost node of the left subtree

Example: Delete P from our tree:

Before:          After:
     P                O
    /               /
   O   R            G
  /               /  G               A   M
/                     A   M                   R

P has two children (O and R). O (left child) takes P’s spot. R (right subtree) attaches to M, the rightmost node in O’s subtree.

Note: Some textbooks use a different method (replacing with the inorder predecessor or successor). ACSL uses the method described above - be sure to follow it on the contest.

Priority queues (heaps)

A min-heap is a complete binary tree where each parent is smaller than its children. The minimum value is always at the root.

Inserting into a min-heap

Add the new element at the next available position (left to right, top to bottom)
Bubble up: compare with parent, swap if smaller, repeat until the heap property is restored

Deleting the minimum

Replace the root with the last element
Bubble down: compare with children, swap with the smaller child if needed, repeat

Example: Build a min-heap from: 5, 3, 8, 1, 4

After 5:     5

After 3:     3      ($3 < 5$, swap)
            /
           5

After 8:     3
            /            5   8

After 1:     1      ($1 < 5$, swap; $1 < 3$, swap)
            /            3   8
          /
         5

After 4:     1
            /            3   8
          /          5   4

Common mistakes

Stack: popping in wrong order. The last pushed item comes out first.
BST: inserting equal values. ACSL typically skips duplicates or specifies behavior. Read the problem.
Traversal confusion. Remember: $In = L, Root, R$ , $Pre = Root, L, R$ , $Post = L, R, Root$ .
Heap: not a BST. In a heap, left child is NOT necessarily smaller than right child. Only the parent-child relationship matters.

Contest strategy

Stack/queue traces: ~30 seconds (just track the state carefully)
BST construction: ~45 seconds (draw the tree as you go)
Traversals: ~30 seconds (follow the L-Root-R pattern literally)
Heaps: ~60 seconds (draw each step of the bubble-up/down)