Which of the following are true of an adjacency list compared with an adjacency matrix? (More than one may be correct.)

It uses O(V + E) space rather than O(V²)

Testing whether a specific edge exists is slower

Enumerating a vertex’s neighbours is faster for a sparse graph

It uses O(V + E) space rather than O(V²)

Testing whether a specific edge exists is slower

Enumerating a vertex’s neighbours is faster for a sparse graph

It cannot represent a directed graph

In the worst case, searching a binary search tree with n nodes takes:

O(n), because the tree may degenerate into a path

Trees, Binary Search Trees, Heaps and Graph Representations

Almost everything in this chapter is counting, and the first thing to settle is the convention for height, because a question is unanswerable without it and most sources do not say. This chapter counts height in edges, so a single node has height 0 and a binary tree of height h has at most 2^h+1 − 1 nodes and at least h + 1. If a question's numbers come out one off, check whether it counts nodes instead. With that fixed, three counting results carry most of the marks. In any binary tree the number of leaves is one more than the number of nodes with two children — n₀ = n₂ + 1 — regardless of shape, which turns many questions into one subtraction. The number of distinct binary search trees on n distinct keys is the nth Catalan number: 5 for three keys, 14 for four, 42 for five, and it counts shapes as well, because a BST's shape determines its key placement completely. And in an array-based heap of n elements, the leaves are the last ⌈n/2⌉ positions and the internal nodes the first ⌊n/2⌋, so a 100-element heap has exactly 50 of each and a height of ⌊log₂100⌋ = 6. The one asymptotic result worth knowing precisely rather than roughly is that building a heap from an unsorted array is O(n), not O(n log n) — the bound is loose because most nodes are near the bottom and sift down only a step or two. Graph representations then close the chapter, and the only thing to hold is the trade: an adjacency matrix answers “is there an edge?” in O(1) and costs O(V²) space however few edges there are, while an adjacency list costs O(V + E) and answers the same question in O(degree).

Counting Nodes, Leaves and Shapes

Binary trees, with height counted in edges
Quantity	Formula	Example
Max nodes at height h	2^h+1 − 1	h = 3 → 15
Min nodes at height h	h + 1	h = 3 → 4 (a path)
Height of a complete tree with n nodes	⌊log₂n⌋	n = 100 → 6
Leaves against two-child nodes	n₀ = n₂ + 1	Holds for every shape
Distinct BSTs on n distinct keys	Catalan Cₙ	n = 5 → 42

🎯 Why n₀ = n₂ + 1, and why it does not depend on the shape

Count edges two ways. A tree with n nodes has n − 1 edges. Each node contributes edges equal to its number of children, so the total is 0·n₀ + 1·n₁ + 2·n₂. Setting those equal and substituting n = n₀ + n₁ + n₂ gives n₀ = n₂ + 1 immediately, with n₁ cancelling out — which is exactly why the shape is irrelevant and why one-child nodes never appear in the relation. The practical use is that a question giving any two of the three counts hands you the third for free: a tree with 20 leaves has 19 nodes with two children, whatever it looks like. It was checked here against all 42 five-node shapes by brute force, not just derived.

⚠️ Preorder plus inorder determines a tree; preorder plus postorder does not

Inorder is the traversal that tells you where the split is: the root is located in the preorder, and its position in the inorder separates the left subtree from the right. Take that away and the information is gone — preorder and postorder together cannot distinguish a node with only a left child from the same node with only a right child, so two different trees share both traversals. The exception worth remembering is that for a full binary tree, where every node has zero or two children, preorder and postorder are enough, because the ambiguous single-child case cannot arise. A question offering two traversals is usually testing exactly this, and the answer turns on whether inorder is one of them.

Heaps in an Array, and Why Building One Is Linear

A binary heap of n elements in an array
Quantity	Value	For n = 100
Leaves	⌈n/2⌉ — the last half	50
Internal nodes	⌊n/2⌋ — the first half	50
Height	⌊log₂n⌋	6
Build from an unsorted array	O(n)	Not O(n log n)
n successive inserts	O(n log n)	A different operation

🎯 Why heapify is O(n) although each sift is O(log n)

The loose bound multiplies n nodes by log n work each and gets O(n log n). The tight bound notices that most nodes are near the bottom and have almost nothing to sift through: half the nodes are leaves and cost 0, a quarter sit one level up and cost at most 1, an eighth cost at most 2. Summing n/2^k+1 nodes doing k work each over all levels gives a series that converges to about 2n, hence O(n). Building a heap by inserting n elements one at a time is genuinely O(n log n), because each insert sifts up from a leaf and the deep positions are the common ones — the mirror image of the argument. Two operations that sound the same and differ by a log factor, and questions do ask which one is being performed.

One more heap fact is asked often enough to be worth stating: the minimum of a max-heap must be a leaf, because any internal node is greater than its children. So finding it requires inspecting all ⌈n/2⌉ leaves — 50 comparisons for a 100-element heap — and there is no shortcut, which is the price a heap pays for being a partial rather than a total order.

Two Ways to Store a Graph

Adjacency matrix against adjacency list
Operation	Matrix	List
Space	O(V²) always	O(V + E)
Is there an edge (u, v)?	O(1)	O(degree of u)
Enumerate all neighbours of u	O(V)	O(degree of u)
Add an edge	O(1)	O(1) at the head
Suits	Dense graphs, E ≈ V²	Sparse graphs, E ≪ V²

The choice is decided by density, and the crossover is not subtle: a graph with a million vertices and two million edges needs about three million list entries and would need a million million matrix cells. That is why every practical graph algorithm is written against adjacency lists, and why a traversal is quoted as O(V + E) rather than O(V²) — the bound is a statement about the representation as much as about the algorithm.

Key takeaways

Fix the height convention first: counted in edges, a single node has height 0.
A binary tree of height h has at most 2^h+1 − 1 nodes and at least h + 1.
In every binary tree n₀ = n₂ + 1 — leaves are one more than two-child nodes, whatever the shape.
Distinct BSTs on n distinct keys is the nth Catalan number: 5, 14, 42 for n = 3, 4, 5.
Preorder plus inorder fixes a tree; preorder plus postorder does not, except for a full binary tree.
In an array heap of n, leaves are the last ⌈n/2⌉ and internal nodes the first ⌊n/2⌋.
Heapify is O(n); inserting n elements one by one is O(n log n) — two different operations.
The minimum of a max-heap is a leaf, so finding it costs ⌈n/2⌉ comparisons.
Matrix: O(V²) space, O(1) edge test. List: O(V + E) space, O(degree) edge test.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

How many distinct binary search trees can be formed from 5 distinct keys?
Numerical answer — type the value.
Show answer
Answer: 42
The count is the fifth Catalan number, 42. The recurrence is the reason: choose any key as the root, and if i keys fall to its left then Cᵢ × C₄₋ᵢ trees follow, summed over all five choices of root. The sequence runs 1, 2, 5, 14, 42, 132. Note that this also counts the distinct shapes of a 5-node binary tree — the same 42 — because once a shape is fixed, the BST property determines which key goes where, with no freedom left. The count of labelled binary trees is a different question: 42 × 5! = 5040, and a question saying "labelled" is asking for that instead.
A binary tree has 20 leaves. How many of its nodes have exactly two children?
Numerical answer — type the value.
Show answer
Answer: 19
n₀ = n₂ + 1 in every binary tree, so n₂ = 20 − 1 = 19. The relation comes from counting edges twice: a tree with n nodes has n − 1 edges, and the edges also total n₁ + 2n₂, and eliminating n gives the result with n₁ vanishing. That vanishing is why the answer needs no information about the shape or about how many nodes have one child — a fact worth trusting, because the question deliberately withholds both. Total node count is not determined: any n₁ ≥ 0 is consistent with 20 leaves.
Building a binary heap from an unsorted array of n elements using the standard bottom-up heapify takes:
1. O(n log n)
2. O(n)
3. O(log n)
4. O(n²)
Show answer
Answer: B — O(n)
O(n). The loose analysis multiplies n nodes by O(log n) per sift and reaches O(n log n), but that overcounts badly: half the nodes are leaves and sift nothing, a quarter sift at most one level, an eighth at most two. Summing (n/2^k+1) × k over the levels converges to about 2n. Option A is the right answer to a different operation — inserting the n elements one at a time, where each new element sifts up from a leaf and the deep positions are the common case, giving a genuine O(n log n). Both build a heap and they differ by a log factor, so the wording of the question decides the answer.
A max-heap holds 100 elements in an array. In the worst case, how many elements must be examined to find the minimum?
Numerical answer — type the value.
Show answer
Answer: 50
The minimum of a max-heap must be a leaf, since every internal node exceeds its children. In an array heap of n the leaves are the last ⌈n/2⌉ positions, so for n = 100 there are 50 of them and all must be compared — there is no ordering among leaves to exploit. This is the cost of a heap being a partial order: it gives O(1) access to the maximum and nothing at all at the other end, which is why a structure needing both ends uses two heaps or a different design entirely. Answering 1 or log n treats the heap as if it were sorted, which it is not.
Which pair of traversals always determines a binary tree uniquely?
1. Preorder and postorder
2. Preorder and inorder
3. Level order alone
4. Postorder alone
Show answer
Answer: B — Preorder and inorder
Preorder and inorder. Preorder names the root; inorder says how many keys lie to its left, which splits the remaining sequence into the two subtrees, and the argument recurses. Inorder is the only traversal carrying that split information, which is why every working pair includes it — postorder and inorder work too. Preorder and postorder do not: a root with only a left child and the same root with only a right child produce identical sequences in both, so two distinct trees share them. The exception is a full binary tree, where no node has exactly one child and the ambiguity cannot arise — a question adding the word "full" is switching the answer to A.
Which of the following are true of an adjacency list compared with an adjacency matrix? (More than one may be correct.)
1. It uses O(V + E) space rather than O(V²)
2. Testing whether a specific edge exists is slower
3. Enumerating a vertex’s neighbours is faster for a sparse graph
4. It cannot represent a directed graph
Show answer
Answer: A — It uses O(V + E) space rather than O(V²); B — Testing whether a specific edge exists is slower; C — Enumerating a vertex’s neighbours is faster for a sparse graph
A, B and C, which together are the whole trade. The list stores only edges that exist, so space is O(V + E) (A) and walking one vertex's neighbours costs O(degree) rather than scanning a whole row of V cells (C). The price is that answering "is (u, v) an edge?" means searching u's list, O(degree), where the matrix answers in O(1) (B). D is false — a directed graph is if anything more natural in a list, since the edge is simply stored once, in u's list only. The decision between them is density: a graph with a million vertices and two million edges is unrepresentable as a matrix and unremarkable as a list.
With height counted in edges, the maximum number of nodes in a binary tree of height 4 is:
1. 15
2. 31
3. 16
4. 32
Show answer
Answer: B — 31
Levels 0 through 4 hold at most 1, 2, 4, 8 and 16 nodes, totalling 2⁵ − 1 = 31. The formula is 2^h+1 − 1 with height in edges. Option A is the answer for height 3, and it is what you get from the same formula under the other convention, where height counts nodes and a single node has height 1 — which is exactly why the convention has to be stated before the question can be answered. Option D drops the −1, forgetting that a full level of 16 sits on top of 15 already there.
In the worst case, searching a binary search tree with n nodes takes:
1. O(log n) always
2. O(n), because the tree may degenerate into a path
3. O(1) after the first search
4. O(n log n)
Show answer
Answer: B — O(n), because the tree may degenerate into a path
A BST search costs O(h), and h can be anything from ⌊log₂n⌋ up to n − 1: inserting keys in sorted order produces a tree that is one long path, and searching it is a linear scan with pointer-chasing overhead. So the worst case is O(n). Option A is the balanced case and is what the structure is usually sold on, which is why the distinction matters — and it is exactly the gap that AVL and red-black trees exist to close, by enforcing O(log n) height at the cost of rebalancing work on every insert. A question saying "balanced" or "AVL" is asking for O(log n); a plain BST is not entitled to it.