Nested todo list with subtasks

A todo list where any task can have subtasks, to any depth, like checklists nested inside a document:

• add(title, parent=None) -> id, appended as the parent's last child.
• complete(id) and reopen(id).
• move(id, new_parent, index=None): re-parent or reorder.
• delete(id): removes the task and its subtasks.
• render() -> str: an outline with [x] or [ ] and two spaces of indent per level.
• progress(id) -> (done, total) over the leaf tasks under it.

Ask how completion propagates; the product rules decide the code:

• Completing a parent completes all its subtasks (you would not leave children open under a done parent).
• A parent becomes done automatically when its last open child is completed, and becomes open again when a child is reopened or an open child is added.

Store tasks in a dict id -> Task(title, done, parent, children: list of ids). Ordered child lists keep the outline order; the parent pointer makes walking up cheap.

Invariant: a task with children is done exactly when all its children are done. Every mutation restores it:

• complete(id): mark the whole subtree done (walk down), then walk up: each ancestor becomes done if all its children are now done; stop at the first one that is not.
• reopen(id): mark the task open (and, by the invariant, if it has children, they must be reopened too, or it would be "done" again; reopen the subtree), then walk up marking ancestors open, stopping at the first already open.
• add under a done parent: the new open child makes the parent and its done ancestors open.
• delete and move change a parent's children, so re-evaluate the old parent (and the new one) by walking up.

Moves must refuse to move a task under itself or its descendants: walk up from the new parent; if you meet the task, reject.

Progress counts leaves: the number of done leaf tasks and the total under a subtree. O(subtree). For a dashboard of huge lists, cache (done, total) per task and update along the path on each change, O(depth) per update.

import itertools
from dataclasses import dataclass, field
from typing import Dict, List, Optional, Tuple


@dataclass
class Task:
    title: str
    parent: Optional[int]
    done: bool = False
    children: List[int] = field(default_factory=list)


class TodoList:
    def __init__(self) -> None:
        self.tasks: Dict[int, Task] = {}
        self.roots: List[int] = []
        self._ids = itertools.count(1)

    # ---- structure --------------------------------------------------------------
    def add(self, title: str, parent: Optional[int] = None) -> int:
        if parent is not None and parent not in self.tasks:
            raise KeyError(parent)
        tid = next(self._ids)
        self.tasks[tid] = Task(title, parent)
        self._siblings(parent).append(tid)
        self._refresh_up(parent)
        return tid

    def delete(self, tid: int) -> None:
        task = self.tasks[tid]
        self._siblings(task.parent).remove(tid)
        for t in self._subtree(tid):
            del self.tasks[t]
        self._refresh_up(task.parent)

    def move(self, tid: int, new_parent: Optional[int], index: Optional[int] = None) -> None:
        node = new_parent
        while node is not None:
            if node == tid:
                raise ValueError("cannot move a task under itself")
            node = self.tasks[node].parent
        task = self.tasks[tid]
        old_parent = task.parent
        self._siblings(old_parent).remove(tid)
        siblings = self._siblings(new_parent)
        siblings.insert(len(siblings) if index is None else index, tid)
        task.parent = new_parent
        self._refresh_up(old_parent)
        self._refresh_up(new_parent)

    # ---- completion ---------------------------------------------------------------
    def complete(self, tid: int) -> None:
        for t in self._subtree(tid):
            self.tasks[t].done = True
        self._refresh_up(self.tasks[tid].parent)

    def reopen(self, tid: int) -> None:
        for t in self._subtree(tid):
            self.tasks[t].done = False
        self._refresh_up(self.tasks[tid].parent)

    # ---- views ------------------------------------------------------------------
    def render(self) -> str:
        lines: List[str] = []

        def walk(ids: List[int], depth: int) -> None:
            for t in ids:
                task = self.tasks[t]
                lines.append(f"{'  ' * depth}[{'x' if task.done else ' '}] {task.title}")
                walk(task.children, depth + 1)

        walk(self.roots, 0)
        return "\n".join(lines)

    def progress(self, tid: int) -> Tuple[int, int]:
        leaves = [t for t in self._subtree(tid) if not self.tasks[t].children]
        return sum(self.tasks[t].done for t in leaves), len(leaves)

    # ---- helpers ------------------------------------------------------------------
    def _siblings(self, parent: Optional[int]) -> List[int]:
        return self.roots if parent is None else self.tasks[parent].children

    def _subtree(self, tid: int) -> List[int]:
        out, stack = [], [tid]
        while stack:
            t = stack.pop()
            out.append(t)
            stack.extend(self.tasks[t].children)
        return out

    def _refresh_up(self, tid: Optional[int]) -> None:
        """Restore 'a parent is done iff all its children are' from tid upward."""
        while tid is not None:
            task = self.tasks[tid]
            if task.children:
                want = all(self.tasks[c].done for c in task.children)
                if want == task.done:
                    return                       # nothing above can change
                task.done = want
            tid = task.parent

_refresh_up stops at the first ancestor whose state does not change: nothing above it can change either, so most updates touch only a few tasks. A task with no children keeps whatever state it was given (an emptied parent stays as it was).

• add: O(depth). complete / reopen: O(subtree + depth). delete: O(subtree + siblings + depth).
• move: O(depth + siblings) (list removal and insertion are linear in the sibling count).
• render and progress: O(subtree).

1. Persistence. Store tasks as rows (id, parent_id, position, done, title). Positions as fractional keys (or strings between neighbors) let a move update one row instead of renumbering siblings.
2. Collaboration. Two people moving tasks at once can create a cycle that neither move creates alone. Apply moves on a server in order and re-run the cycle check at apply time, or use a tree CRDT that resolves conflicting moves deterministically.
3. Large lists. Cache (done, total) per task and update along the path to the root on every change, so progress bars are O(1) to read.
4. Due dates and assignees. "Show me my open tasks due this week" needs an index outside the tree: a map from assignee to tasks, filtered by due date, with the tree only for display.
5. Undo. Record each operation with what it changed (including the subtree's previous done flags for complete), so undo can restore exactly, not just flip states.

Mid-level (L4)

• A tree of tasks with ordered children, add, complete and an indented outline.
• Completing a parent completes its subtasks.
• Tests on a small nested example.

Senior (L5)

• States the invariant (a parent is done exactly when all children are) and restores it on every mutation, stopping the upward walk early.
• Moves that refuse cycles, deletes of whole subtrees, and progress over leaves.
• Tests the tricky cases: adding a child under a done parent, deleting the last open child.

Staff (L6+)

• Persistence with fractional positions, cached progress, and indexes for cross-cutting views.
• Concurrent moves and the cycle problem in collaborative editing.
• Undo that restores previous states exactly.