Programming, Data Structures and Algorithms

In a topological order every edge points forward, so each vertex comes after all of its predecessors. The edges are \(P \to Q\), \(R \to Q\), \(Q \to S\), \(Q \to V\), \(S \to U\) and \(V \to T\): P and R must precede Q, Q must precede S and V, S must precede U, and V must precede T.

• A and C fail: both place Q before R, which breaks the edge \(R \to Q\).
• B holds: after P, R, Q come V, S, U, T, so U follows S and T follows V.
• D holds: P, R, Q, S, V, T, U also respects every edge.

More than one order is valid because the chains \(S \to U\) and \(V \to T\) do not depend on each other.

Answer: B, D

Height here is the number of edges on the longest root-to-leaf path, so a single node has height 0; the bounds in the options use this convention.

• A holds: if \(n_{2}\) nodes have two children, the tree has exactly \(L = n_{2} + 1\) leaves, and those \(n_{2}\) nodes are internal, so \(L \le I + 1\).
• B holds: the longest path alone has \(H + 1\) nodes, and levels 0 to \(H\) hold at most \(1 + 2 + \dots + 2^{H} = 2^{H+1} - 1\) nodes.
• C holds: the first \(H\) nodes on the longest path are internal, and internal nodes can sit only on levels 0 to \(H - 1\), which hold at most \(2^{H} - 1\) nodes.
• D fails: a path of height 2 has a single leaf, so \(H \le L\) breaks, and a perfect tree has \(2^{H}\) leaves, more than \(2^{H-1}\).

Answer: A, B, C