We closed module 5 with a confession: hashing is unbeatable when you hand it an exact key, but it falls silent when asked things like "give me the tasks ordered by id" or "all the tasks with priority between 1 and 3". Its keys are scattered on purpose, with no notion of neighborhood or order. To answer those questions we need a structure that keeps the data organized, and that structure is the tree. In this lesson you will learn what a tree is, master its vocabulary (root, leaf, height, depth...), build the TreeNode class for generic trees, and use it to model something TaskFlow has been crying out for: the projects → categories → tasks → subtasks hierarchy. Everything that follows in this module — binary trees, BSTs, AVL trees, B-trees, heaps — rests on the vocabulary and intuition of this lesson.

1. From hash to tree: why we need hierarchy and order
2. What a tree is: definition and properties
3. Terminology: the vocabulary we'll use all module long
4. Generic trees in Python: the TreeNode class
5. Hierarchical TaskFlow: projects, categories, tasks, and subtasks
6. Traversing a generic tree with recursion
7. Trees in real life

Let's review what each structure you already have in TaskFlow can do:

The last three rows share something: they ask about relationships between elements (order, range, hierarchical membership), not about an isolated element. Every structure you know so far is linear: each element has, at most, one predecessor and one successor. Trees break that linearity: an element can have several successors. That small difference changes everything.

This module will tackle the three gaps in order: hierarchy today (generic trees), order and ranges in 06-04 (binary search trees), and along the way, in 06-07, we'll settle module 4's promise: opening up heapq from the inside.

A tree is a hierarchical data structure made of nodes connected by edges, satisfying three properties:

• There is exactly one root node, which has no parent.
• Every non-root node has exactly one parent.
• There are no cycles: following edges, you never return to a node you've already visited.

A useful consequence: a tree with n nodes has exactly n - 1 edges (every node except the root contributes the edge that connects it to its parent). And between the root and any node there is a single path — no alternative routes.

A note we'll pick up again in module 7: formally, a tree is a special case of a graph (connected and acyclic). We leave it here as a mention; in general graphs a node may have several "parents" and there will be cycles, and that will demand new techniques.

Notice that trees in computer science are drawn upside down compared to botanical ones: root at the top, leaves at the bottom. It's pure convention, but it's universal.

This vocabulary will show up in all seven lessons that follow; it's worth nailing down. Referring to the diagram above:

Two subtleties that confuse everyone at first:

• Depth is measured from the root downward (each node has its own); height is measured from the leaves upward (a node's height is that of the longest path to a leaf below it; the tree's height is the root's height). The root has depth 0 and maximum height; a leaf has height 0 and variable depth.
• The word subtree is the key to recursion: each child of a node is, in turn, the root of a complete tree. A tree is "a node + a list of smaller trees". That recursive definition is what makes almost every algorithm in this module naturally recursive — the recursion from module 3 is going to work hard here.

In a generic (or n-ary) tree, each node can have any number of children. The natural implementation: a value and a list of children. Compare it with the Node from module 2 — there, next was one reference; here, children is a list of references. That's the entire leap from linear to hierarchical.

Point by point:

• value can be anything: in TaskFlow it will sometimes be a string (a project or category name) and sometimes a task's dict.
• children starts as an empty list: every node is born a leaf and stops being one when it receives children.
• add_child returns the added child: that way we can write backend = project.add_child(TreeNode("Backend")) and keep hanging things off backend.
• There's no wrapping "Tree" class: keeping the root is enough. From it, everything is reachable, just as everything in the LinkedList was reachable from self.head.

Until today, TaskFlow stored tasks in flat structures: a linked list, a queue, a hash table. But any real user organizes their work in levels: projects that contain categories, which contain tasks, which in turn have subtasks (remember module 3's nested subtasks, the ones that gave us a RecursionError? They were a tree asking for permission to exist). Let's build it:

Notice the elegance: we haven't written a single new line of structure to go from 2 levels to 4. The list of children makes no distinction between "a project containing categories" and "a task containing subtasks"; the hierarchy can grow as deep as the user wants.

What good is the tree if we can't query it? Systematic traversals (with names, guaranteed order, and iterative versions) are the subject of 06-03; here we'll see the basic pattern they all derive from: process the node and recurse on each child. First, counting nodes:

Read the function in light of the recursive definition of a tree: "the size of a tree is 1 (its root) plus the sum of the sizes of its subtrees". The base case (None → 0) and the calls on strictly smaller structures guarantee termination — exactly the two requirements we studied in module 3. Since there are no cycles and every node has a single parent, each node is visited exactly once: cost O(n).

Now something flashier: printing the tree with indentation, the way tree does in the terminal. Each node's depth becomes indentation:

Output:

The depth parameter travels with each recursive call incremented by 1: it's the direct translation of the definition "depth = number of edges from the root". And a note of honesty you already know from module 3: if the tree were absurdly deep (thousands of levels), Python's call stack would protest with a RecursionError; there we learned to convert recursion into iteration with an explicit stack, and in 06-03 we'll apply that technique to traversals.

Trees are not an academic invention; you probably use several every minute:

• The file system: /home/joan/projects/taskflow/main.py is a root→leaf path. Folders are internal nodes, files are leaves, and tree is our show function.
• A web page's DOM: <html> is the root, and every nested tag is a child. When JavaScript reads element.children, it's reading a children list like ours.
• Org charts: top management as the root, departments as subtrees. "How many people report (directly or indirectly) to X?" is count_nodes(X) - 1.
• Menus and categories in any application or online store — exactly our hierarchical TaskFlow.
• Language syntax: the Python interpreter itself turns your code into a tree (the AST) before executing it.

Whenever you see data with a "contains" or "reports to a single superior" relationship at work, think tree.

• Confusing height and depth. Mnemonic: depth is measured from the root (how many floors below the surface are you?); height from the leaves (how tall are you from the ground?). This gets asked constantly in interviews.
• Forgetting the base case in recursive functions. Without the if node is None: return 0, calling count_nodes(None) (say, on an empty tree) blows up with AttributeError. Every tree algorithm must decide what to do with the empty tree.
• Creating cycles by accident. If you add a node as a child of one of its own descendants, you no longer have a tree: recursive traversals will never terminate. Structures with legitimate cycles exist — they're the graphs of module 7 — but they require different techniques.
• Sharing the children list between nodes. A Python classic: defining def __init__(self, value, children=[]) with a mutable default list makes all nodes share the same list. Always initialize self.children = [] inside __init__.
• Tip: always keep a reference to the root in a stable variable. Losing a tree's root is losing the whole tree, just like losing head in the linked list.

Write count_tasks(node) that returns how many nodes in the subtree contain a task (i.e., whose value is a dict), ignoring projects and categories. On the lesson's tree it must return 5.

Write depth_of(node, target_id) that returns the depth at which the task with that id sits (the root has depth 0), or None if it doesn't exist. depth_of(root, "T-01a") must return 4.

Write leaves(node) that returns the list of values of all leaves in the subtree. In the lesson's tree, Project: Mobile app is a leaf (it has no content yet), and so are the tasks with no subtasks.

Solution 1

Comment: it's count_nodes with the "1" made conditional. The traversal's structure doesn't change — what changes is what we do at each node. This pattern (fixed traversal, variable action) will repeat throughout the module.

Solution 2

Comment: the important detail is the if result is not None: return result — as soon as one subtree finds the task, we stop exploring its siblings. Without it, the function would keep searching and return None even after having found the target. Also note that searching a generic tree is O(n): with no rule about where each value lives, you potentially have to look at every node. In 06-04 we'll add that rule and search will drop to O(height).

Solution 3

Comment: here the useful base case isn't None but is_leaf(): a leaf returns itself; an internal node delegates and concatenates. That Project: Mobile app shows up among the leaves is correct and revealing: "leaf" is a structural property (having no children), not a semantic one (being a task).

You now have the vocabulary (root, leaf, parent, subtree, height, depth, level) and the tool (TreeNode with its list of children) that will support the entire module, and TaskFlow has finally gained its projects → categories → tasks → subtasks hierarchy — with recursive traversals that reuse what you learned in module 3. But look at the solution to exercise 2: searching this tree still costs O(n), and the order and range questions the hash table left unanswered remain unanswered. The road to the answer starts by restricting the tree: if each node has at most two children, with distinguished positions (left and right), tremendously powerful mathematical properties appear — and on top of them we'll build O(log n) search. That restricted tree is the binary tree, the star of the next lesson.