Lizzy McDSA

Tree

data that branches instead of forming a line; one item on top, each item can lead to several below it (like folders holding folders).

Root

the top node of a tree.

Parent / Child

the node above / the node below.

Leaf

a node with no children.

Edge

a line connecting parent to child.

Height

number of edges on the longest path down from a node.

Binary Tree

each node has at most two children: left and right.

Node (in code)

holds a value plus left and right links to its children.

Tree as a List

no links stored; position alone tells you the relationships: left child = 2i+1, right child = 2i+2, parent = (i-1)//2.

Preorder Traversal

visit root → left → right.

Inorder Traversal

visit left → root → right.

Postorder Traversal

visit left → right → root.

Level Order Traversal

visit top level first, left to right (uses a queue).

Binary Search Tree (BST)

a binary tree with one rule: smaller goes left, bigger goes right, at every node.

BST Insert

go left if smaller, right if bigger, stop at an empty spot.

BST Search

follow one path down; never look at the whole tree.

BST Delete (3 cases)

no children → just remove; one child → child moves up; two children → copy in the smallest key from the right subtree, then delete that key.

Insertion order matters

the same keys inserted in different orders produce trees of different heights/shapes (sorted input → a long skinny “line” tree).

Priority Queue

serves the most urgent item first, not the one that arrived first.

Heap

a binary tree with two rules: shape rule (filled level by level, no gaps) and order rule (every parent ≤ its children, for min-heap).

Min-Heap

parent is always smaller than its children; smallest value sits on top.

Max-Heap

parent is always bigger than its children; biggest value sits on top.

Heap stored in a list

same index formulas as a tree: left child = 2i+1, right child = 2i+2, parent = (i-1)//2. heap[0] is always the smallest (min-heap).

Insert (heap)

add the new value at the end of the list, then swap it upward until it’s no longer smaller than its parent.

Extract Min

take the root (smallest), move the last item to the top, then swap it downward (sift down) until the heap rule is restored.

sift_down

the helper that repeatedly swaps a value down until it’s smaller than both its children; used by both extract_min and heapify.

Heapify

turn any list into a valid heap by running sift_down on every parent node, from the last parent back to the root; O(n).

Heap Sort

heapify the list, then repeatedly extract the minimum until empty; results come out sorted. O(n log n) average and worst case.

Heap vs. Merge/Quick Sort

heap sort guarantees O(n log n) like merge sort, but (in its classic form) needs only O(1) extra space, unlike merge sort’s O(n).

Python’s heapq

a built-in min-heap module (heappush, heappop) that works just like the hand-built version.

The Problem

searching a plain list for an item gets slower as the list grows (O(n)); a hash table finds things in about one step (O(1)) regardless of size.

Hash Function

takes a key (e.g. a name) and turns it into a bucket number; same key always gives the same number.

Good hash function rules

same key → same number every time; spreads different keys across different buckets; fits the result inside the table size (using % size).

Collision

when two different keys hash to the same bucket number; unavoidable since there are far more possible keys than buckets.

Chaining

handles collisions by letting each bucket hold a list; colliding keys just get added to that bucket’s list.

Open Addressing

handles collisions by finding another empty slot instead of using a list.

Linear Probing

a type of open addressing: if a slot is taken, try the next slot (+1, +2, +3...).

Quadratic Probing

a type of open addressing: if a slot is taken, jump by increasing squared steps (+1, +4, +9...).

Put

hash the key to find its bucket, then add/update the key-value pair there.

Get

hash the key to find its bucket, then search only that bucket’s list for the value.

Load Factor

number of items stored divided by number of buckets; tells you how full the table is.

Rehashing

when the load factor gets too high (commonly over 0.75), grow the table (e.g. double the buckets) and re-insert every key, since each key’s bucket number depends on the table size.

Hash Table vs. BST

hash table: O(1) average lookup but keys are scattered (no sorted order). BST: O(log n) lookup but keys can be retrieved in sorted order (inorder traversal).

Python’s dict

is literally a hash table under the hood ([]= to put, [] to get, in to check membership).

What is the top node of a tree called?

The root.

Which traversal prints a BST’s keys from smallest to biggest?

Inorder traversal (left, root, right).

In the list form, the node at index 2 has its left child at which index?

Index 5, since the left child is at 2i + 1 = 2(2) + 1 = 5.

Insert 10, 20, 30 into an empty BST. What is the height? Which order gives a shorter tree?

The height is 2, because each key is bigger than the last, so the tree becomes a line (10, then 20 to its right, then 30 to the right of that). Inserting 20 first, then 10 and 30 (for example 20, 10, 30), gives a shorter tree with height 1.

In a min-heap stored in a list, where is the smallest value?

At the top of the heap, which is index 0 (heap[0]).

When you insert a value, where does it go first?

At the end of the list (the next open spot in the tree). Then it swaps up with its parent while it is smaller than the parent.

The node at index 2 has its children at which two indexes?

Index 5 and index 6, since the left child is 2i + 1 = 5 and the right child is 2i + 2 = 6.

Is [2, 1, 3] a min-heap? Why or why not?

No. The parent 2 is bigger than its left child 1, which breaks the order rule that every parent must be smaller than or equal to its children. The smallest value (1) should be on top.

Two different keys get the same bucket number. What is that called?

A collision.

A table has 10 buckets and 8 items. What is the load factor? Should it grow?

The load factor is 8 / 10 = 0.8. Yes, it should grow, because 0.8 is above 0.75 and the table is getting crowded.

After rehashing, why must every key be hashed again?

The bucket number depends on the table size (for example % 7 before and % 14 after). With a new size, the same key can get a different bucket number, so each key has to be hashed again to find its correct new spot.

ord(‘B’) is 66 and ord(‘o’) is 111. With our hash function and 7 buckets, where does ‘Bo’ go?

Bucket 2. The letter codes add up to 66 + 111 = 177, and 177 % 7 = 2.