Micro-questions over the trees module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why trees exist
1. What is the limitation of linear structures that trees fix?
Answer
Arrays and linked lists store things in one line. Plenty of real data is not a line but a hierarchy — things containing things — and forcing a hierarchy into a line loses the structure.
2. Give three real-world examples of trees.
Answer
A file system (folders containing folders), the DOM of a web page, and a company org chart.
3. What is a tree, informally?
Answer
A collection of nodes connected by edges, starting from a single root, where every node has exactly one parent except the root, and nothing loops back.
B. The vocabulary
4. What is a node?
Answer
One item in the tree — a value plus pointers to the nodes beneath it.
5. What is an edge?
Answer
The link between two nodes; the line drawn between a parent and a child.
6. What is the root?
Answer
The single node at the very top, the one with no parent. A tree has exactly one, and it is where every traversal begins.
7. What is a parent?
Answer
A node that points directly down to another. Every node has exactly one parent, except the root, which has none.
8. What is a child?
Answer
A node directly below a parent.
9. What are siblings?
Answer
Nodes sharing the same parent.
10. What is a leaf?
Answer
A node with no children — the end of a branch. Also called a terminal node.
11. What is an internal node?
Answer
Any node that is not a leaf, i.e. one with at least one child.
12. What is an ancestor?
Answer
Any node on the path from the root down to a given node.
13. What is a descendant?
Answer
Any node reachable by moving downwards from a given node.
14. What is a subtree, and what does it make possible?
Answer
A node together with all of its descendants. Every node is the root of its own subtree — which is what makes tree algorithms naturally recursive.
15. What is the degree of a node?
Answer
How many children it has. A leaf has degree 0.
16. What is a level?
Answer
How far down a node sits. The root is at level 0, its children at level 1, and so on.
C. Height versus depth
17. Define depth.
Answer
How far down a node is from the root — count edges root → node. The root has depth 0.
18. Define height.
Answer
The longest path from a node down to a leaf — count edges node → leaf. A leaf has height 0.
19. What is the height of the tree?
Answer
The height of the root node.
20. Give the memory trick for telling them apart.
Answer
Depth measures how deep you sink down from the surface (the root). Height measures how tall a tower is built up from the ground (a leaf).
21. In the reference tree A→(B,C), B→(D,E), C→F — give depth of D and height of B.
Answer
Depth of D = 2 (A→B→D). Height of B = 1 (B→D). Height of the whole tree = 2.
22. Can a node have the same height and depth?
Answer
Yes — for example a leaf at depth 0, which is a single-node tree, has both equal to 0. In general they measure opposite directions and are unrelated.
D. The formal definition
23. Give the formal definition of a tree.
Answer
A connected, acyclic graph. With nodes it has exactly edges.
24. Why exactly edges?
Answer
Every node except the root is the child end of exactly one edge — one edge per node, minus the parentless root.
25. What are the two consequences of having no cycles?
Answer
- There is exactly one unique path between the root and any node.
- Trees are inherently recursive — any node can be viewed as the root of a smaller tree.
26. Why is almost every tree algorithm written recursively?
Answer
Because solving a problem on a tree means solving the identical problem on its left and right subtrees. The structure is self-similar, so the code is too.
E. The kinds of tree
27. What is a binary tree?
Answer
Every node has at most two children, called left and right.
28. What is an n-ary tree? A general tree?
Answer
N-ary: up to children per node — a file system is one. General: any number of children, no limit — the DOM is one.
29. What is a binary search tree?
Answer
A binary tree with a rule added: everything in a node’s left subtree is smaller than it, everything in the right subtree is larger. That rule is what makes a tree searchable.
30. What is an AVL tree?
Answer
A BST that rebalances itself after every insertion and deletion, keeping height close to . Strictly balanced: fast lookups, slightly more expensive modifications.
31. What is a red-black tree, and why is it what libraries actually use?
Answer
Another self-balancing BST, with looser balance rules than AVL. Rebalancing is cheaper and lookups slightly slower — a better trade for general use, which is why Java’s TreeMap and C++‘s std::map are red-black trees.
32. What is a B-tree, and why is its shape wide and shallow?
Answer
Each node holds many keys and has many children. The wide, shallow shape means fewer disk reads to reach any key, which is why almost every database index is a B-tree.
33. What does a B+ tree change, and why do databases prefer it?
Answer
All the actual data lives in the leaves, and the leaves are linked in a chain. That chain makes range queries very fast — “everything between these two values” — which is what databases mostly do.
34. What is a trie?
Answer
A tree where the path spells a word rather than any node holding one. Built for prefix questions. See tries.
35. How is a heap’s rule weaker than a BST’s, and why is that deliberate?
Answer
Each parent is merely ordered relative to its children, with no rule between siblings. The weakness makes the rule cheap to maintain, which is the whole point. See heaps.
36. What is a segment tree for?
Answer
Storing a summary of a range in each node, so questions like “what is the sum between positions 5 and 900?” are answered in while still allowing updates.
37. What is a Fenwick tree, and what is its trade against a segment tree?
Answer
Also called a binary indexed tree. It answers the same range questions with less memory and much shorter code, at the cost of being harder to reason about.
38. What is a suffix tree for?
Answer
Storing every suffix of a string, making substring search extremely fast. Heavily used in bioinformatics for DNA matching.
39. What is a k-d tree for?
Answer
It splits space rather than a list, answering “which stored point is nearest to this one?” — nearest-neighbour search in graphics and machine learning.
40. Why does this course concentrate on binary trees?
Answer
Because that is where the core ideas live: recursion over a hierarchy, the relationship between height and cost, and the fact that balance is what makes a tree fast. The rest are variations once those are clear.
F. Boundaries
41. What does a tree degenerate into when it loses its balance?
Answer
A linked list — every node with one child, height , and every claim collapsing to .
42. How does the graphs folder define a tree differently?
Answer
Without a root: a connected acyclic graph. Rootedness is something you add by choosing a node, not part of the underlying object. See trees and forests.
43. Summarise a tree in one sentence.
Answer
A hierarchy with exactly one path to each node — self-similar, so recursion is the natural tool, and fast only as long as it stays short.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Trees — the module
- Binary Trees — Question Bank — the next bank
- Linked Lists — Question Bank — what an unbalanced tree becomes
Software engineering
Infrastructure & security
Computer science
Hardware & engineering