Data structures: stack, tree, hash table, directed graph

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• What does a DFA state correspond to after subset construction? from Lesson 0.2.3
• Write the regular definition of an identifier. from Lesson 0.2.2
• What information does a symbol table entry hold? from Lesson 0.1.3

1 · The Story

📖

Rhea runs the mailroom

Rhea runs the mailroom of Translation House. Four habits keep it working.

The tray pile. Incoming trays are put on top of a single pile, and she always works on the top tray. If a tray says “wait, first finish this other job”, the new tray goes on top, and when it is done she returns to the tray beneath, exactly where she left it.

The org chart. Mrs. Desai is at the top; under her, Mira, Kabir and Rhea; under Mira, her two assistants Asha and Bina; under Kabir, Chetan. To announce something to everyone, Rhea visits people in a fixed order.

The pigeonholes. There are 10 boxes. Each staff number goes to box (number mod 10). Finding someone’s mail means looking in one box, not searching the whole room; two people can share a box.

The corridor map. The corridors are one-way. Rhea draws rooms as dots and corridors as arrows. Some chores must follow others (sort before stamp, stamp before deliver); if the chores ever went round in a circle, nothing could be started.

2 · Predict First

🤔

Rhea puts trays 1, 2, 3 on the pile, finishes one, then adds tray 4 and finishes two. Which trays has she finished, in order? Write your guess down. The answer is in the vault.

3 · Core Concept

Stack

A stack keeps items in a pile with access only at the top: push adds on top, pop removes the top, top looks at it. Last in, first out (LIFO).

Compilers use stacks for matching brackets, for parsing (Phase 2) and for function calls (Phase 5).

Tree

A tree is a set of nodes with one root; every other node has exactly one parent; nodes with no children are leaves; the others are internal nodes. Children are ordered left to right. The height is the number of edges on the longest root-to-leaf path.

Two visiting orders matter:

• preorder: visit the node, then its children left to right (each in preorder);
• postorder: children first (left to right, each in postorder), then the node.

Phase 2 draws the structure of a program as a tree; Phase 3 computes values by visiting it in postorder.

Hash table

A hash table stores items in an array of m buckets. A hash function h maps a key to a bucket number, e.g. h(k) = k mod m. Two keys in one bucket are a collision; with chaining, each bucket holds a list. Lookup takes about constant time on average, which is why symbol tables are usually hash tables keyed by the name.

Directed graph

A directed graph has nodes and directed edges (arrows) u → v. v is a successor of u; u is a predecessor of v. A path follows arrows; a cycle is a path that returns to its start. A graph with no cycle is a DAG (directed acyclic graph): its nodes can always be listed so that every arrow points forward in the list.

Compilers use DAGs to share repeated computations (Phase 4) and directed graphs of code pieces for optimization (Phase 6).

Story → compiler term

4 · Visual

The tray pile after push 1, push 2, push 3, pop (3), push 4: only the top is reachable.

The org chart as a tree. Preorder: Desai Mira Asha Bina Kabir Chetan Rhea. Postorder: Asha Bina Mira Chetan Kabir Rhea Desai.

Hash table with m = 10 after inserting 23, 43, 13, 27.

A DAG of chores: arrows show “must come before”. No cycle, so an order exists: sort, stamp, weigh, deliver.

5 · Worked Examples

Example 1 Easy

Starting empty: push 1, push 2, pop, push 3, push 4, pop, pop. What is popped, and what is left?

Solution

Popped in order: 2, 4, 3. Left on the stack: [1]. Like Rhea’s trays: the newest tray is always the next one handled.

Example 2 Medium

For the org chart tree, give the preorder and postorder, the number of leaves and the height.

Solution

Preorder: Desai, Mira, Asha, Bina, Kabir, Chetan, Rhea. Postorder: Asha, Bina, Mira, Chetan, Kabir, Rhea, Desai. Leaves: Asha, Bina, Chetan, Rhea = 4. Height 2 (Desai → Mira → Asha).

Postorder lists every person after everyone under them, which is the order in which department reports can be added up.

Example 3 GATE

Keys 23, 43, 13, 27 go into a hash table of size 10 with h(k) = k mod 10 and chaining. Which bucket has the longest chain, and how long is it?

Solution

23, 43 and 13 all go to bucket 3; 27 goes to bucket 7. The longest chain is in bucket 3, length 3: two collisions there. As in Rhea’s pigeonholes, three staff share box 3.

6 · Shortcuts

⚡

Pop-order check: push 1, 2, 3, … in order and pop only when the number you need next is on top. If the number you need is buried under others, the sequence is impossible. Valid when: questions on valid pop sequences when items are pushed in a fixed order.

⚡

Postorder = children first. Write each node right after its last child is finished. Valid when: trees of any shape.

⚡

Collisions = keys − distinct buckets used. Valid when: chaining, counting keys that land in an already used bucket.

7 · GATE Traps

⚠️

• Pop removes the most recent push, not the oldest (that would be a queue).
• Preorder visits the parent first; postorder visits it last.
• A collision does not lose data with chaining; it only makes one chain longer.
• A DAG may have a node with two parents; only a tree forbids that.

8 · Memory Hook

🧠

Stack = tray pile, tree = org chart, hash table = pigeonholes, graph = one-way corridors.

9 · Connect the Dots

All primers are done. Phase 1 opens the first department: how the lexical analyzer uses regular expressions and automata to turn characters into tokens, and how it records names in a hash-table symbol table.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markStack

Start empty: push A, push B, push C, pop, pop, push D, pop, push E. How many items are on the stack at the end?

Numerical answer: ________

Q2MCQ1 markTraversal

A tree has root P with children Q (left) and R (right); Q has children S and T; R has child U. The postorder is:

• (A) P Q S T R U
• (B) S T Q U R P
• (C) S Q T P U R
• (D) P R U Q T S

Q3NAT1 markHashing

Keys 15, 22, 29, 8, 36, 43 are inserted into a table of size 7 with h(k) = k mod 7 and chaining. How many keys land in an already occupied bucket?

Numerical answer: ________

Q4MSQ1 markGraphs

Which statements are true?

• (A) A DAG contains no cycle.
• (B) In a tree, every node except the root has exactly one parent.
• (C) A directed graph with a cycle can list its nodes so that every edge points forward.
• (D) In a DAG a node may have two predecessors.

Q5MCQ1 markLIFO

Which structure is last-in, first-out?

• (A) queue
• (B) stack
• (C) hash table
• (D) tree

11 · Rule Card

• Stack: push/pop/top, LIFO.
• Tree: root, parent, children, leaves; height = longest root-to-leaf path in edges.
• Preorder: node, then children. Postorder: children, then node.
• Hash table: h(k) = k mod m; collisions handled by chaining; average O(1) lookup → symbol tables.
• Directed graph: nodes, edges u → v, successors/predecessors, paths, cycles; DAG = no cycle.

12 · Concept Ledger

stackpush / pop / topLIFOtreenoderoot / parent / childleafheightpreorderpostorderhash tablehash functionbucketcollision / chainingdirected graphedgesuccessor / predecessorpathcycleDAG

13 · Answer Vault