Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverse the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where $$1 \le k < n:$$ reverse (s, 1, k);
reverse (s, k+1, k);
reverse (s, 1, n);

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?