The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Tree Exercises

Next ►
►

Module loaded: generic trees and their terminology (06-01), binary trees and their arithmetic (06-02), the four traversals (06-03), the BST with ranges (06-04), the AVL that never degenerates (06-05), the databases' B-tree (06-06), and the heap that opened up heapq (06-07). This lesson adds no theory: it's the gym where those pieces combine over TaskFlow in six progressive exercises — from warming up with traversals to three absolute technical-interview classics (validating a BST with its famous trap, rebuilding a tree from its traversals, and top-k with a heap of size k). Give each one a serious attempt before looking at the solution: the statements include hints, and wrestling with a tree for ten minutes teaches more than reading ten solutions.

Contents

  1. Exercise 1: an X-ray of the project tree (height and counting)
  2. Exercise 2: auditing the BST property (with the classic trap)
  3. Exercise 3: the k-th highest-priority task (partial inorder)
  4. Exercise 4: budget per subtree (postorder)
  5. Exercise 5: rebuilding a tree from preorder + inorder
  6. Exercise 6: top-k urgent tasks with a heap of size k
  7. Commented solutions

The starting data

All the exercises use the module's classes: TreeNode (06-01, with value and its children list), BinaryNode (06-02), SearchTree/BSTNode (06-04), and Heap (06-07). For the first two exercises on the generic tree, this project:

def T(id, title, priority, hours):
    return {"id": id, "title": title, "priority": priority,
            "status": "pending", "hours": hours}

project = TreeNode(T(1, "Launch TaskFlow 2.0", 1, 8))
backend = project.add_child(TreeNode(T(2, "Backend", 1, 5)))
frontend = project.add_child(TreeNode(T(3, "Frontend", 2, 3)))
docs = project.add_child(TreeNode(T(4, "Documentation", 3, 6)))
api = backend.add_child(TreeNode(T(5, "API v2", 1, 12)))
db = backend.add_child(TreeNode(T(6, "Migrate DB", 2, 9)))
api.add_child(TreeNode(T(7, "Authentication", 1, 4)))
frontend.add_child(TreeNode(T(8, "Panel redesign", 2, 10)))
graph TD
    A["1: Launch 2.0 (8h)"] --> B["2: Backend (5h)"]
    A --> C["3: Frontend (3h)"]
    A --> D["4: Documentation (6h)"]
    B --> E["5: API v2 (12h)"]
    B --> F["6: Migrate DB (9h)"]
    E --> G["7: Authentication (4h)"]
    C --> H["8: Panel redesign (10h)"]

Exercises

Exercise 1: an X-ray of the project tree

Write two functions on the generic tree: generic_height(node) (the subtree's height, with the module's convention: empty = −1, leaf = 0) and count_per_level(root) (a dict of level → number of nodes). For project they must give height 3 and {0: 1, 1: 3, 2: 3, 3: 1}. Hint: the first calls for postorder (height rises from children to parents); the second falls out naturally from 06-03's level-order traversal, or from a preorder that carries the depth along.

Exercise 2: auditing the BST property

Write is_bst(node) that decides whether a binary tree (nodes with key) satisfies the search property. Start by writing the incorrect version — the one that only compares each node with its direct children — and find a tree that fools it; then write the correct one, propagating (minimum, maximum) bounds. Mandatory test tree:

graph TD
    A((10)) --> B((5))
    A --> C((15))
    B --> D((3))
    B --> E((12))

Each parent is greater than its left child and smaller than its right one... and yet it is not a BST. Why?

Exercise 3: the k-th highest-priority task

On the AVL/BST index keyed by (priority, id) from 06-04/06-05, write kth_most_urgent(tree, k) that returns the task occupying position k (1-indexed) in urgency order — without materializing the full list: the inorder must stop as soon as it finds the k-th. Hint: a counter that travels through the recursion and a return value that cuts off exploration (the same early-stop pattern as depth_of in 06-01).

Exercise 4: budget per subtree

On the project tree, write budget(node) that returns a dict of id → accumulated hours for its subtree (its own plus all descendants) in a single O(n) pass. For the root it must give 57; for Backend (id 2), 30. Hint: pure postorder — it's 06-03's accumulated_hours generalized to n children, additionally storing each intermediate result.

Exercise 5: rebuilding a tree from preorder + inorder

A colleague exported a TaskFlow binary tree as two lists: preorder = [10, 6, 3, 8, 15, 12, 20] and inorder = [3, 6, 8, 10, 12, 15, 20]. Write rebuild(preorder, inorder) that returns the root of the only binary tree compatible with both (no duplicate keys). Hints: the first key of the preorder is always the root (06-03); its position in the inorder splits that list into left and right subtrees; recurse on the halves. Bonus question: why isn't preorder alone enough?

Exercise 6: top-k urgent tasks with a heap of size k

TaskFlow archives hundreds of thousands of tasks and the dashboard only shows the k most urgent (smallest (priority, id)). Sorting everything costs O(n log n) and materializes what nobody sees. Write top_k(tasks, k) — with tasks an iterable of dicts — that does it in O(n log k) by maintaining a heap of at most size k. Hint: if the heap is a min-heap, what must live at its root so you can decide in O(1) whether a new task makes the top? (Revisit 06-07's max-heap note: negation is your friend.)

Solutions

Solution 1: an X-ray of the tree

def generic_height(node):
    if node is None:
        return -1
    if not node.children:                  # leaf: height 0
        return 0
    return 1 + max(generic_height(c) for c in node.children)

from collections import deque

def count_per_level(root):
    counts = {}
    queue = deque([(root, 0)])             # travel with the depth, as in 06-03
    while queue:
        node, level = queue.popleft()
        counts[level] = counts.get(level, 0) + 1
        for c in node.children:
            queue.append((c, level + 1))
    return counts

print(generic_height(project))     # 3
print(count_per_level(project))    # {0: 1, 1: 3, 2: 3, 3: 1}

Comment: generic_height generalizes 06-02's binary height by swapping max(left, right) for max over the children list — and it needs the explicit leaf case, because max() over an empty sequence raises ValueError (in the binary version, the -1 of the None children covered it). Information flows from children to parents: postorder. count_per_level flows the other way (depth descends from parents to children), which is why BFS with a (node, level) tuple fits — module 4's deque once more; with module 5's defaultdict(int) the counting line would be even cleaner. Two questions, two directions of flow, two traversals: choosing a traversal is answering "which way does the information flow?".

Solution 2: auditing the BST property

The naive version and its counterexample:

def is_bst_WRONG(node):
    """INCORRECT: only compares with the direct children."""
    if node is None:
        return True
    if node.left and node.left.key >= node.key:
        return False
    if node.right and node.right.key <= node.key:
        return False
    return is_bst_WRONG(node.left) and is_bst_WRONG(node.right)

# The statement's tree: 10 -> (5 -> (3, 12), 15)
root = BinaryNode(10); root.key = 10           # or use BSTNode directly
# ... (analogous construction with a key on each node)
print(is_bst_WRONG(root))    # True  <- a lie!

12 is the right child of 5 (12 > 5: the naive version applauds) but it lives in 10's left subtree, where everything must be < 10. The BST property speaks about entire subtrees, not parent-child pairs — the warning repeated since 06-04, and the exact difference from the heap, whose property really is local (which is why 06-07's is_min_heap compared only against the parent and was correct). The good version propagates the allowed range:

def is_bst(node, minimum=float("-inf"), maximum=float("inf")):
    """Each descent NARROWS the allowed (minimum, maximum) interval."""
    if node is None:
        return True
    if not (minimum < node.key < maximum):
        return False
    return (is_bst(node.left, minimum, node.key) and
            is_bst(node.right, node.key, maximum))

print(is_bst(root))    # False: by the time we reach 12, the interval was (-inf, 10) — but 5 < 12

Comment: going left, the current node becomes the ceiling (maximum); going right, the floor (minimum). 12 is evaluated against the (5, 10) interval inherited from its two ancestors, and fails. One O(n) pass, and the number-one candidate for a tree interview question. An equally valid alternative: generate the inorder and check it comes out strictly increasing — same cost, though the bounds version stops earlier at the first failure.

Solution 3: the k-th task

def kth_most_urgent(tree, k):
    def partial_inorder(node, remaining):
        """Returns (task found or None, how many are left to skip)."""
        if node is None:
            return None, remaining
        # 1) first, the entire left subtree (the most urgent ones)
        found, remaining = partial_inorder(node.left, remaining)
        if found is not None:
            return found, 0                        # got it: propagate without looking further
        # 2) the node itself consumes one slot
        remaining -= 1
        if remaining == 0:
            return node.value, 0
        # 3) only if still needed, the right subtree
        return partial_inorder(node.right, remaining)

    return partial_inorder(tree.root, k)[0]

# With the 30-task index from 06-05 (priorities (i % 3) + 1):
print(kth_most_urgent(index, 1)["id"])    # 3  (the first priority-1 task)
print(kth_most_urgent(index, 11)["id"])   # 1  (the first priority-2 task)

Comment: it's 06-03's inorder with two additions: a remaining counter that travels along and is decremented at the "visit node" step, and the immediate propagation of the find, which avoids exploring the pending subtrees — the early stop of depth_of (06-01). Cost: O(height + k) — for small k on an AVL, logarithmic, versus the O(n) of materializing the full inorder() and indexing. Architect's note: serious library trees offer this operation in pure O(log n) by storing in each node its subtree size (to skip entire subtrees by counting instead of walking); the idea of annotating nodes with aggregated data is exactly that of the next exercise.

Solution 4: budget per subtree

def budget(node, result=None):
    """dict id -> accumulated hours of the subtree. One pass, O(n)."""
    if result is None:
        result = {}
    total = node.value["hours"]                    # its own hours...
    for c in node.children:
        budget(c, result)                          # (the children fill in their own)
        total += result[c.value["id"]]             # ...plus each child's accumulated total
    result[node.value["id"]] = total
    return result

budgets = budget(project)
print(budgets[1])   # 57  (the whole launch)
print(budgets[2])   # 30  (Backend: 5 + (12+4) + 9)
print(budgets[5])   # 16  (API v2: 12 + 4)

Comment: textbook postorder — a parent can't know its total until each child has deposited its own in result, so the recursion over the children goes before the final sum. The finesse lies in reusing the children's accumulated totals (result[c.value["id"]]) instead of recomputing their subtrees: each node is visited once and the cost is O(n); the naive variant calling "sum the subtree" for every node repeats work and scales to O(n²) on deep trees — the same height-per-node trap we avoided in _height_and_validity (06-05). With this dict, TaskFlow's manager answers "how much does Backend cost with everything hanging from it?" in O(1): a module-5 hash index fed by a module-6 traversal, working as a team.

Solution 5: rebuilding from preorder + inorder

def rebuild(preorder, inorder):
    if not preorder:
        return None
    root = BinaryNode(preorder[0])             # preorder: the root ALWAYS comes first
    cut = inorder.index(preorder[0])           # its position splits the inorder in two
    left_in, right_in = inorder[:cut], inorder[cut + 1:]
    left_pre = preorder[1:1 + len(left_in)]    # the preorder is split by SIZE
    right_pre = preorder[1 + len(left_in):]
    root.left = rebuild(left_pre, left_in)
    root.right = rebuild(right_pre, right_in)
    return root

tree = rebuild([10, 6, 3, 8, 15, 12, 20], [3, 6, 8, 10, 12, 15, 20])
# Verification: regenerate both traversals with 06-03's functions
pre, ino = [], []
def walk_pre(n):
    if n: pre.append(n.value); walk_pre(n.left); walk_pre(n.right)
def walk_ino(n):
    if n: walk_ino(n.left); ino.append(n.value); walk_ino(n.right)
walk_pre(tree); walk_ino(tree)
print(pre)   # [10, 6, 3, 8, 15, 12, 20]  — matches
print(ino)   # [3, 6, 8, 10, 12, 15, 20]  — matches: it's the tree from 06-03/06-04

Comment: each traversal contributes half the information — the preorder says who's in charge (its first element is the root), the inorder says who ends up on each side (what precedes the root is its left subtree). Once the inorder reveals the left side's size, the preorder splits in the same proportions and recursion does the rest. Answer to the bonus question: preorder alone doesn't determine the tree — [2, 1] could be "2 with left child 1" or "2 with right child 1"; you need the inorder to disambiguate (or to know the tree is a BST, in which case the inorder comes free: it's the preorder, sorted!). Professional polish: inorder.index(...) is O(n) on every call (O(n²) total in the worst case); with a value → position dict built once — module 5 to the rescue again — the entire reconstruction drops to O(n).

Solution 6: top-k urgent tasks

def top_k(tasks, k):
    """The k tasks with the smallest (priority, id), sorted. O(n log k)."""
    heap = Heap()               # min-heap of NEGATED keys => max-heap of urgency
    for t in tasks:
        key = (-t["priority"], -t["id"], t)        # negate: the WORST of the top sits at the root
        if len(heap) < k:
            heap.insert(key)
        elif key > heap.peek_min():                # more urgent than the worst one kept?
            heap.extract_min()                     # out with the worst...
            heap.insert(key)                       # ...in with the new one. O(log k)
    result = []
    while len(heap):
        result.append(heap.extract_min()[2])       # they come out worst to best...
    result.reverse()                               # ...reverse: best to worst
    return result

import random
tasks = [{"id": i, "title": f"Task {i}", "priority": random.randint(1, 5),
          "status": "pending"} for i in range(1, 100001)]
random.shuffle(tasks)
for t in top_k(tasks, 5):
    print(t["priority"], t["id"])    # the 5 priority-1 tasks with the smallest ids, in order

Comment: the idea to internalize — to retain the k smallest, the heap keeps at most k elements and its root is the worst of the good ones (the largest of the current top), thanks to 06-07's key negation: min-heap of negated values = max-heap of originals. That way, each new task is compared in O(1) against that living threshold: if it doesn't beat it, it doesn't even enter (the massively most frequent case); if it does, one extract + insert in O(log k). Total O(n log k) with O(k) memory: with n = 100,000 and k = 5, trivial arithmetic compared with sorting a hundred thousand tasks to display five. It's the exact pattern of any "top 10" over a stream that doesn't fit (or isn't worth) sorting — and the (-priority, -id) pair additionally guarantees the correct tiebreak: among equals in priority, the smaller id wins.

Common Mistakes and Tips

  • Validating the BST against the parent and calling it a day (exercise 2): the mistake is so widespread that interviewers deliberately build the tree with the 12. Inherited bounds or increasing inorder; there is no third way.
  • Recomputing subtrees instead of reusing accumulated totals (exercises 1 and 4): calling "height/sum of the subtree" inside every node blows the cost up to O(n²). Information flowing from children to parents is computed once, in postorder, and stored.
  • Forgetting the early stop in recursive searches (exercise 3): without propagating the find, the traversal keeps visiting entire subtrees for nothing — correct but O(n), which was exactly what was forbidden.
  • Splitting the lists wrong when rebuilding (exercise 5): the inorder is split by the root's position; the preorder, by the left side's size. Crossing the criteria produces phantom trees that later fail to reproduce the traversals — always verify by regenerating them.
  • Using a min-heap of un-negated keys for the top-k of smallest (exercise 6): it leaves the best at the root, which is exactly the one you don't want to evict. To retain the k smallest you evict the largest: max-heap (negation) mandatory.
  • Final tip: all six exercises fit in a single file with the module's classes; keep it. The validator, the reconstruction, and the top-k are the three most-asked tree questions in interviews, and budget + kth_most_urgent will return as building blocks in module 8's projects.

Conclusion

End of module 6, and the loot is serious: TaskFlow has a real project hierarchy with budgets per subtree, an index ordered by (priority, id) that answers ranges and k-th queries without breaking a sweat (and which, thanks to the AVL, doesn't degrade even when ids arrive sorted), certainty about what its database does underneath (B+), and an O(log n) urgency inbox whose engine holds no more secrets. And you have the judgment: the question decides the structure — exact key to the hash, order and ranges to the balanced tree, "the next most urgent" to the heap, disk to the B-tree. But notice the silent assumption that has held up the entire module: every node has exactly one parent. The subtask belongs to one task, the task to one category, and that uniqueness is what made possible the traversals without visited, the clean recursion, the balance. Now think about TaskFlow's real dependencies: "deploy the API" can't start until "migrate the DB" and "configure the server" are finished — a task that depends on several at once, and maybe two others depend on it. That's no longer a tree: paths cross, possible cycles appear (does A depend on B which depends on A?), and hierarchy falls short. You need the most general structure in the course, the one the tree was just a well-behaved special case of: the graph. Module 7 awaits with its representation, the BFS and DFS we've been sowing for two modules — with the visited set promised in module 5 finally in action — and shortest paths. See you among nodes and edges.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved