Trees and Binary Trees Questions and Answers

Answer: D

The tree is left skewed.

Inorder visits left subtree, node, right subtree; postorder visits left subtree, right subtree, node. The two orders agree only if no node has a right subtree, because then both reduce to 'left subtree, then node'. A binary tree in which every node has only a left child is left skewed.

In a right-skewed tree the inorder sequence runs from root to leaf and postorder from leaf to root, the reverse of each other. Any balanced tree with two or more levels has right children, so its orders differ.

Answer: A

The key gives 3.

Seven nodes fill a complete binary tree exactly: 1 node at the root, 2 on the next level and 4 on the last. That is 3 levels, and counting levels, the height is 3, which is how the key reads the question.

Counting edges instead, the same tree has height 2, which is option C, and a skewed 7-node tree would be taller still. The paper states neither a convention nor the shape of the tree, so the item is loose. The key gives A, so it is kept; note that textbooks that define height as the number of edges on the longest path give 2 for the complete tree. Option D, 7, is only the height of a degenerate chain counted in nodes, and 4 fits no 7-node complete tree.

Answer: A

The maximum number of nodes at level L is \(2^{L}\), counting the root as level 0.

Each node has at most two children, so each level can hold at most twice as many nodes as the one above: 1 at level 0, 2 at level 1, 4 at level 2, and \(2^{L}\) at level L.

Some books number the root as level 1, and with that convention the same count is written \(2^{L-1}\). The key follows the root-at-level-0 convention. \(2^{L} - 1\) is a different quantity, the total number of nodes in a full tree of L levels, and \(L^{2}\) grows far too slowly.

Answer: D

Root first, then left, then right is preorder traversal.

The three depth-first traversals of a binary tree are named after where the root is visited. Preorder visits the root before its subtrees (root, left, right), inorder visits it between them (left, root, right), and postorder visits it after them (left, right, root).

Level order is breadth-first: it visits the nodes level by level from the top, left to right, using a queue, rather than following the root-left-right pattern.

Answer: A

A binary tree with 4 levels has at most 15 nodes.

Level i (counting the root as level 1) can hold at most \(2^{i-1}\) nodes, so a full tree of h levels has:

\[ \begin{aligned} N &= 1 + 2 + 4 + 8 \\ &= 2^{4} - 1 = 15 \end{aligned} \]

16 is \(2^{4}\), forgetting the minus one. 31 is the count for 5 levels, and 14 falls one short.

Answer: B

The key's answer is 1.

A binomial tree B_k has a root whose sub-trees are themselves binomial trees B_k-1, B_k-2, ..., B₁, B₀. Read from the lowest height upward, the sub-trees are B₀, B₁, B₂ and so on, so the second one is B₁, of order 1, in any binomial tree of order 2 or more.

Counted from the tallest sub-tree instead, the second is B_k-2, whose order depends on k, so the question has a single answer only on the first reading. Order 0 is the first sub-tree on that reading, and 2 is the third.

Answer: C

The preorder traversal is ABDECF.

In a postorder traversal the root comes last, so DEBFCA has A as the root. The nodes before it split into the left and right subtrees. B comes after D and E and before F and C, so B is the root of the left subtree with D and E as its children, and C is the root of the right subtree with F as its child.

\[ \text{Preorder} = A\,B\,D\,E\,C\,F \]

Option (A), ABFCDE, and option (B), ADBFEC, do not match the shape given by the postorder, and (D) is wrong since ABDECF is among the options.

Answer: C

A hierarchical relationship between elements is represented by a tree.

A tree has a root and levels of children below it, with a parent and child relation between elements, as in an organisation chart or a directory structure. A dequeue (A) is a linear list with insertions and deletions at both ends, and a priority queue (B) orders elements by priority, but neither has a hierarchy of parents and children. 'All of the above' (D) is wrong for the same reason.

Answer: C

A binary tree of depth d with the root at level 0 needs at least one node at each of the levels 0, 1, up to d, and so the minimum number of nodes is d + 1. This is a skewed tree in which each level has one node.

The values \(2^{d} - 1\) and \(2^{d+1} - 1\) are the largest numbers of nodes of trees of depth d - 1 and d, and the value d is one node too few. Option C is correct.