Tree-shaped data and recursive visitation

Intermediate Recursion & structural decomposition

Created by Pavel · 29.04.2026 at 19:04 UTC

Decision trees, aggregation hierarchies (region → store → SKU), and JSON documents all share tree-shaped structure: nodes with children, leaves without. Recursive traversals—preorder (node before children), postorder (children before node), inorder for binary search trees—encode different when-to-process policies.

For data products, tree walks appear when you flatten OLAP hierarchies for ML features, validate schema trees, or serialise nested pandas MultiIndex levels to a wire format. The recursive pattern is: handle the current node, then recurse into each child with the same function.

General trees use lists of children; binary trees often use (value, left, right) triples or small classes. The implementation detail changes; the structural recursion does not.

collections.deque (if you rewrite breadth-first iteratively): [1].

Sources

[1]https://docs.python.org/3/library/collections.html#collections.deque Return to text

University approvals: 0

Tasks

Question 1

In a preorder depth-first walk on a rooted tree, you typically:

Hint

Root-first for preorder.

Visit all leaves before any internal node

Visit the current node before recursing into its subtrees

Sort keys at every node

Visit children in random order only once globally

Question 2

You build a feature vector from a small taxonomy tree: parent nodes sum the contributions of children. Which traversal pattern matches bottom-up aggregation?

Hint

Children contribute before the parent combines.

Preorder only

Level-order with a single queue pass

Postorder: resolve children before combining at the parent

Reverse preorder on sorted keys

Question 3

Binary tree nodes are tuples (label, left, right) with left/right either None or nested tuples. Implement collect_labels(tree) returning labels in preorder.
Example: (1,(2,None,None),(3,None,None)) → [1,2,3].

Hint

Root label first, then left subtree, then right.

def collect_labels(tree):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

3 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Recursion & structural decomposition
Difficulty: Intermediate
Completed: 0 users

Creator

Pavel