Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 11
Trees (Lecture 11)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
A leaf is a node that:
No children. (a) is the root; a node with one child (c) is internal.
-
With height counted in edges, the height of a tree with exactly one node is:
Height counts edges, and a single node has none. -1 (a) is the empty tree, which makes 1 + max(-1, -1) = 0 work for a leaf.
-
The largest number of nodes a binary tree of height 3 can hold is:
Levels 0 to 3 hold at most 1 + 2 + 4 + 8 = 15 = 2h+1 - 1. 7 (a) is height 2; 8 (b) is the size of level 3 alone.
-
The smallest possible height of a binary tree with 100 nodes is:
⌊ log2 100 ⌋ = 6: height 6 holds up to 127 nodes, height 5 only 63. 99 (d) is the tallest possible height, a chain.
-
A binary tree is a binary search tree when, for every node x:
The property is about whole subtrees. (a) is the weaker parent–child check, which W11-M20 shows is not enough; (c) is the heap property of Week 12.
-
In the tree Q, the right child of the root's left child is:
The root is 30, its left child 15; 20 > 15 went right. 17 and 25 are 20's children; 8 is 15's left child.
-
contains(25)on Q compares 25 with how many nodes?30 (go left), 15 (go right), 20 (go right), 25 (found).
-
The worst-case cost of
containson a BST of n nodes, built bydsa/tree.pyfrom values in an unknown order, is:The cost is O(h), and nothing in
dsa/tree.pykeeps h small: sorted input makes h = n - 1. O(log n) (b) is true only while the tree stays short — on average for random input, or always for a balanced tree. -
Which insertion order of 1 to 7 builds the tallest BST?
7 first, then 1, then each value between the last two: every node gets one child, a zigzag chain of height 6. (a) and (b) build the perfect tree of height 2 (W11-S2); (c) has height 3.
-
The pre-order walk of Q is:
Node, then the whole left subtree, then the right. (a) is in-order, (c) level-order, (d) post-order.
-
The post-order walk of Q is:
Both subtrees before the node, so the root 30 is last. (c) is not any of the walks; (d) visits 8 after 17 and 25, which are in a different subtree.
-
Which walk of any BST lists its values in increasing order?
Left subtree (all smaller), node, right subtree (all larger): sorted, for every BST.
-
You save a BST to a file as a list of values, and later rebuild it by inserting the list into an empty tree. To get back the same shape, the list should be the tree's:
Pre-order lists every node before its descendants, so re-inserting it sends each value down the same path to the same place. The in-order walk (a) is sorted and rebuilds a chain; post-order (c) inserts leaves first, so the first value inserted — a leaf — becomes the root.
-
Which walk frees a tree safely in a language where you release memory yourself, and evaluates an expression tree?
Post-order finishes a node's children before the node: free the children while you still hold the links to them, and apply an operator only after both operands have values.
-
level_orderuses a queue rather than the call stack because:Recursion is last in, first out: it finishes the most recent node's subtree before returning. Level-order needs first in, first out — the nodes in the order they were discovered. Memory (a) is not the reason; the queue can be larger than the stack (W11-K3).
-
During
level_orderon Q, the largest number of nodes waiting in the queue at one time is:After dequeuing 45, and again after dequeuing 20, four nodes wait: 8, 20, 40, 60 and then 40, 60, 17, 25 (W11-S3).
-
Deleting a node with two children,
dsa/tree.pyreplaces its value with:The in-order successor. The largest value of the right subtree (a) is too large: everything else in that subtree is smaller than it, yet would sit on its right.
-
delete(30)on Q. Which value ends up at the root?Right once to 45, then left to 40, which has no left child: 40 is the successor and goes to the root. 25 (b) is the predecessor — also a correct choice in general, but not
dsa/tree.py's. -
The in-order successor of a node with two children never has a left child. Why does that matter to
delete?With no left child, the successor is a leaf or has one (right) child, so it is removed by the easy rule. It need not be a leaf (c): in Lecture 11's second example the successor 10 has a right child, 14.
-
A student's
is_validchecks, at every node, only that the left child is smaller and the right child larger. It:It accepts the lecture's tree 8 → 3 → 9, where 9 is a right child of 3 but sits in 8's left subtree. It never rejects a valid BST, and it is O(n) — but wrong.
-
The expression tree for
(2 + 3) * 4is walked in post-order. The result is:Left operand, right operand, operator:
2 3 + 4 *, the postfix form of Lecture 06. (a) is pre-order; (b) is in-order, which has lost the brackets and means 14, not 20. -
AVL trees and red-black trees:
Both keep extra data in each node — a height or a colour — and rotate nodes after changes so that the height stays O(log n). They are beyond the bylaw (named, not examined);
dsa/tree.pyis unbalanced (a).
19 marks
Written questions
5 written questions (19 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 19
-
Define root, leaf, parent, subtree, depth and height, using the tree Q as the example for each. Why does a tree of n nodes always have exactly n - 1 edges?
Model answer and marking points
- Root: the one node with no parent — 30. Leaf: a node with no children — 8, 17, 25, 40, 50. Parent: 20 is the parent of 17 and 25.
- Subtree: a node and everything below it — the subtree of 45 is {45, 40, 60, 50}.
- Depth: edges from the root down to the node — 17 has depth 3. Height: edges on the longest path down to a leaf — 15 has height 2 (15, 20, 17), and the tree's height is 3.
- n - 1 edges: every node except the root has exactly one parent, so exactly one edge comes into it from above; the root has none. Counting edges by the node they lead into gives n - 1.
-
State the BST property. Give a tree in which every parent–child pair is in the right order but which is not a BST, and explain how
is_validmust be designed to reject it. What is its cost?Model answer and marking points
- Property: for every node x, every value in x's left subtree is smaller than x and every value in its right subtree is larger.
- Counter-example: root 8, left child 3, right child 10, and 9 as the right child of 3. Each pair is in order (3 < 8, 10 > 8, 9 > 3), but 9 is in 8's left subtree.
contains(9)goes right at 8 and never finds it. - Design: carry an allowed range (low, high) down the recursion, starting unbounded at the root. Going left from x sets high = x; going right sets low = x. A node outside its range makes the tree invalid; the empty tree is valid. Test "no bound" with
is not None, not truthiness, or a bound of 0 is lost. - Cost: each node is checked once, O(1) work: O(n) time, O(h) stack.
-
Describe the three cases of BST deletion. For the two-children case, explain why the in-order successor may take the deleted value's place, and why removing the successor is always easy.
Model answer and marking points
- Leaf: set the parent's link to it to
None. - One child: point the parent's link at that child; the child's whole subtree moves up one level and stays in order, because it lay on the same side of every ancestor as the deleted node.
- Two children: find the in-order successor — right once, then left until there is no left child. Copy its value into the node, then remove the successor's node.
- Why the successor fits: it is larger than everything in the left subtree (they are smaller than the deleted value, which is smaller than it), and it is the smallest value of the right subtree, so smaller than all that remain there.
- Why removal is easy: it was reached by going left until there was no left child, so it has no left child: it is a leaf or has one right child — one of the easy cases. Watch the case where the successor is the node's own right child: then the link to change is the node's
right(W11-B3). - Always: keep the parent; if the node is the root,
self.rootchanges. O(h).
- Leaf: set the parent's link to it to
-
Name the four traversals of a binary tree, give the order of each, and for each say one thing it is used for and why it suits that use.
Model answer and marking points
- Pre-order (node, left, right): serialising a tree — re-inserting the list rebuilds the same shape, because every node comes after its ancestors; also prefix notation.
- In-order (left, node, right): listing a BST's values in sorted order without sorting; checking a BST (strictly increasing); range queries.
- Post-order (left, right, node): freeing a tree (children before the parent whose links you still need), evaluating an expression tree (operands before operator), computing sizes and heights (a node's answer needs its children's).
- Level-order (by depth, left to right): printing a tree level by level; the nearest nodes first — the idea of breadth-first search. Needs a queue.
- (Marks: one for the orders, one per two correct uses with reasons.)
-
"A BST gives O(log n) search." When is that true, and when is it false? Explain with the height, give an insertion order that makes it false, and name the cure. Compare a BST with a sorted array for search, insert and listing in order.
Model answer and marking points
- True when the tree is short: every operation walks one path, O(h), and h can be as small as ⌊ log2 n ⌋. On random insertion orders h is O(log n) on average — measured in Lecture 11, 26.6 for 4,096 values.
- False when the tree is tall: inserting sorted values (1, 2, …, n) makes every new value the largest so far, so it always goes right: a chain of height n - 1, and search is O(n) — about 205 µs against 1.8 µs at n = 4,096 in the lecture's measurement.
- Cure: a balanced BST — AVL or red-black — which re-shapes itself with rotations to keep h = O(log n) in the worst case (beyond this course); or, with all values known in advance, insert the middle first (W11-C4).
- Against a sorted array: search O(log n) in both (the BST only while short); insert O(n) in the array (shifting) against O(h) in the BST (no moves); listing in order O(n) in both (in-order walk).