Data Structures & Algorithms Trees & Hierarchical Structures Flashcards

24 sample cards from the Trees & Hierarchical Structures deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. Describe a left rotation on node $x$ (with right child $y$) and what it preserves.

   $y$ becomes the new subtree root; $x$ becomes $y$'s left child; $y$'s original left subtree becomes $x$'s right subtree. It preserves the BST inorder ordering and runs in $O(1)$ time by relinking a constant number of pointers. A right rotation is its mirror inverse.

2. Do rotations change the inorder traversal of a BST? Why does this matter?

   No — rotations **preserve the inorder ordering** of keys; they only change the tree's shape/height. This is precisely why balanced BSTs (AVL, Red-Black) can rebalance via rotations without violating the BST property.

3. What is a B-tree of minimum degree (order) $t$, and what are its key properties?

   A B-tree of minimum degree $t \geq 2$ is a balanced multiway search tree where: every node has at most $2t-1$ keys and at most $2t$ children; every non-root node has at least $t-1$ keys; keys within a node are sorted; and **all leaves are at the same depth**. Height is $O(\log_t n)$.

4. Why are B-trees and B+ trees preferred for databases and filesystems over binary search trees?

   Their high branching factor makes them **shallow**, minimizing the number of slow disk/block accesses (each node maps to a disk page). Height $O(\log_t n)$ with large $t$ means very few I/Os per operation, unlike a binary tree's $\log_2 n$ deeper structure.

5. What is the key structural difference between a B-tree and a B+ tree?

   In a **B-tree**, keys (and their data) live in both internal and leaf nodes. In a **B+ tree**, all actual data/records reside only in the **leaves**; internal nodes hold only separator keys for routing. B+ tree leaves are also linked in a sorted linked list, enabling fast in-order range scans.

6. What is a binary heap and what is the heap-order property for a min-heap vs. a max-heap?

   A binary heap is a **complete** binary tree stored in an array. **Min-heap**: every parent's key $\leq$ its children's keys (root is the minimum). **Max-heap**: every parent's key $\geq$ its children's keys (root is the maximum). It gives no ordering between siblings.

7. For a 0-indexed array representation of a binary heap, give the index formulas for a node's parent, left child, and right child.

   For index $i$: parent $= \lfloor \frac{i-1}{2} \rfloor$, left child $= 2i+1$, right child $= 2i+2$. (For 1-indexed heaps: parent $= \lfloor i/2 \rfloor$, left $= 2i$, right $= 2i+1$.)

8. Describe the sift-up (bubble-up) operation used when inserting into a binary heap.

   Append the new element at the end of the array (next leaf position). Then repeatedly compare it with its parent; if it violates the heap order, swap them. Continue until the parent satisfies the order or the root is reached. Cost $O(\log n)$.

9. Describe the sift-down (heapify) operation used when extracting the root of a binary heap.

   Remove the root, move the last element to the root position, then repeatedly swap it with its **smaller child** (min-heap) / larger child (max-heap) until heap order is restored or a leaf is reached. Cost $O(\log n)$. This underlies extract-min/extract-max.

10. What is the time complexity of building a heap from an unsorted array of $n$ elements, and why is it $O(n)$ rather than $O(n\log n)$?

    **Build-heap runs in $O(n)$**. Applying sift-down from the last internal node up to the root, the work is $\sum_{h} \frac{n}{2^{h+1}} \cdot O(h) = O\!\left(n \sum_{h=0}^{\infty} \frac{h}{2^{h}}\right) = O(n)$, because most nodes are near the bottom with small sift-down cost.

11. Give the time complexities for the core binary heap operations: peek, insert, extract-min/max, and decrease-key.

    **Peek** (find-min/max): $O(1)$. **Insert**: $O(\log n)$. **Extract-min/max**: $O(\log n)$. **Decrease-key / increase-key**: $O(\log n)$. **Build-heap**: $O(n)$. **Delete arbitrary** (given index): $O(\log n)$.

12. How do you find the $k$-th largest element in an array using a heap, and what is the complexity?

    Maintain a **min-heap of size $k$**: iterate through elements, push each; if the heap exceeds size $k$, pop the smallest. After processing, the heap's root is the $k$-th largest. Time $O(n \log k)$, space $O(k)$. (Quickselect gives $O(n)$ average as an alternative.)

13. Describe the K-way merge problem and how a heap solves it efficiently.

    Merge $k$ sorted lists (total $n$ elements) into one sorted output. Use a **min-heap of size $k$** holding the current front element of each list. Repeatedly pop the smallest, output it, and push the next element from that element's list. Time $O(n \log k)$, space $O(k)$.

14. For the Top-K frequent elements problem, describe an efficient heap-based approach and its complexity.

    Count frequencies with a hash map ($O(n)$), then maintain a **min-heap of size $k$** keyed by frequency, popping the least frequent when size exceeds $k$. The heap ends holding the $k$ most frequent. Time $O(n \log k)$. (Bucket sort by frequency gives $O(n)$.)

15. What is a Trie (prefix tree), and what does each node/edge represent?

    A Trie is a tree for storing strings where each **edge represents a character** and each path from the root spells a prefix. Nodes typically hold a map/array of child pointers and a boolean flag marking the end of a valid word. Common prefixes share the same path, saving space.

16. What are the time complexities of insert, search, and prefix-search (startsWith) in a Trie?

    All are $O(L)$ where $L$ is the length of the query string — **independent of the number of stored words $n$**. This is the Trie's key advantage over hashing for prefix queries. Space can be large: up to $O(n \cdot L \cdot \sigma)$ with alphabet size $\sigma$ using array-based children.

17. Give one advantage of a Trie over a hash table for string storage.

    Tries support efficient **prefix queries** (autocomplete, startsWith, longest-prefix matching) and return keys in sorted order, none of which hash tables do naturally. Lookups are $O(L)$ with no hashing collisions, and common prefixes are stored once.

18. What is a Segment Tree and what class of problems does it solve?

    A Segment Tree is a binary tree over an array where each node stores an aggregate (sum, min, max, gcd, …) of a contiguous range. It answers **range queries and point/range updates** on a static-size array, both in $O(\log n)$, using $O(n)$ space (typically a $2n$ to $4n$ array).

19. State the time and space complexities for building, querying, and updating a Segment Tree.

    **Build**: $O(n)$ time. **Range query**: $O(\log n)$. **Point update**: $O(\log n)$. **Range update with lazy propagation**: $O(\log n)$. **Space**: $O(n)$ (allocate about $4n$ or $2n$ for iterative).

20. What is *lazy propagation* in a Segment Tree and why is it needed?

    Lazy propagation defers **range updates** by storing a pending update value at internal nodes and only pushing it down to children when those children are actually visited. Without it, a range update would touch $O(n)$ leaves; with it, both range update and range query stay $O(\log n)$.

21. What is a Fenwick Tree (Binary Indexed Tree, BIT) and what operations does it support?

    A Fenwick Tree is an array-based structure supporting **prefix-sum queries** and **point updates**, each in $O(\log n)$, using only $O(n)$ space. It exploits the binary representation of indices: index $i$ is responsible for a range of length equal to its lowest set bit.

22. In a 1-indexed Fenwick Tree, how do you move to the next index during an update versus during a prefix-sum query?

    Let $\text{lsb}(i) = i \,\&\, (-i)$ (lowest set bit). **Update** (add): move to $i \mathrel{+}= \text{lsb}(i)$, going upward covering ranges. **Prefix-sum query**: move to $i \mathrel{-}= \text{lsb}(i)$, accumulating until $i = 0$. Both take $O(\log n)$ steps.

23. Compare a Fenwick Tree and a Segment Tree for range-sum problems.

    **Fenwick**: simpler, ~$O(n)$ space (single array), lower constant factors, but limited mostly to invertible aggregates (sums) and prefix-based queries. **Segment Tree**: more general (min/max/gcd/assignments, range updates via lazy propagation, arbitrary associative merges) at the cost of more memory (~$4n$) and code complexity. Both query/update in $O(\log n)$.

24. How is a range-sum $\text{sum}(l, r)$ over indices $l..r$ computed from a Fenwick Tree that supports prefix sums?

    Using prefix sums $P(i) = \text{sum}(1..i)$: $$\text{sum}(l, r) = P(r) - P(l-1).$$ Each prefix sum is $O(\log n)$, so a range-sum query is $O(\log n)$. This subtraction trick requires an invertible operation (why Fenwick suits sums but not min/max directly).

What this deck covers

Trees & Hierarchical Structures flashcards FAQ