Recurrence Tree Viz

A general-purpose recursion-tree renderer. Callers describe the tree as a flat nodes array — each node carries an id, an optional parentId, a call-expression label ("fib(3)", "merge(0,5)"), and an optional value (the return value the call produced). The component derives a top-down hierarchical layout: children stack horizontally, parents sit at the centroid of their visible descendants, and an optional value-pill renders under each node once it has returned.

Reach for it whenever the story is the shape of the recursion — fibonacci's exponential branching, merge sort's logarithmic depth, or the post-order completion of a divide-and-conquer call.

Installation

npx shadcn@latest add https://craftbits.dev/r/recurrence-tree-viz.json

Usage

import {
  RecurrenceTreeViz,
  type RecurrenceTreeNode,
} from "@craft-bits/core";
 
const nodes: RecurrenceTreeNode[] = [
  { id: "root", label: "fib(3)", value: 2 },
  { id: "l", parentId: "root", label: "fib(2)", value: 1 },
  { id: "r", parentId: "root", label: "fib(1)", value: 1, tone: "resolved" },
  { id: "ll", parentId: "l", label: "fib(1)", value: 1, tone: "resolved" },
  { id: "lr", parentId: "l", label: "fib(0)", value: 0, tone: "resolved" },
];
 
<RecurrenceTreeViz nodes={nodes} defaultFocusedId="root" />

Drive the focused node from outside (e.g. wire it to a step-through scrubber):

const [focusedId, setFocusedId] = useState(null);
 
<RecurrenceTreeViz
  nodes={nodes}
  focusedId={focusedId}
  onFocusedIdChange={setFocusedId}
/>

Collapse a subtree by passing an explicit expandedIds set — every id in the set has its children rendered; ids outside the set render as leaves:

<RecurrenceTreeViz
  nodes={nodes}
  expandedIds={new Set(["root"])}
/>

Understanding the component

1. Flat nodes, derived hierarchy. Instead of a recursive node.children shape, the API takes a flat list. Each node carries an id and parentId so the renderer can group siblings, walk in DFS, and discard orphans whose parents were not supplied. The first node with no parent becomes the root.
2. Two-pass layout. First pass walks DFS to seed each leaf's horizontal slot. Second pass walks top-down placing each internal node at the centroid of its visible children. This handles unbalanced fibonacci trees, single-branch merge-sort spines, and collapsed subtrees without overlap.
3. Focus is one node at a time. focusedId follows the Radix pattern — focusedId plus onFocusedIdChange for controlled mode, defaultFocusedId for uncontrolled. Tapping a node toggles its focus; the focused node gets a thick accent ring and any edge touching it lights up to accent. Tapping the focused node again clears focus.
4. Expansion is a set. expandedIds is a ReadonlySet<string> of ids whose subtrees render. Pass null (the default) to show every subtree. Double-tap a node to toggle its entry in the set. Collapsed subtrees release their horizontal slots so the surviving tree re-balances cleanly.
5. Tone encodes post-order state. Each node accepts a tone of "default" (in-progress), "resolved" (returned), or "dimmed" (pruned). Resolved nodes get an accent border plus tinted background; dimmed nodes drop to ~55% opacity. Combined with the value pill, this lets the same component animate a recursion from root to leaves and back.
6. Reduced motion. usePrefersReducedMotion() collapses node and edge transitions to instant. Focus rings still update on click — just without the spring.

Props

Accessibility

• The outer <svg> is role="img" with a <title> summarising the root call, visible-node count, and the currently focused call (if any).
• Every node carries a tabIndex'd transparent hit circle so keyboard users can tab through nodes; Enter and Space toggle focus exactly like a click.
• Every node's hit area is at least 44 × 44 px even when the visible circle shrinks under compact, satisfying WCAG 2.5.8.
• Color is never the only signal — every node renders its label, and the optional value pill carries the textual return value alongside the accent border.
• Motion respects prefers-reduced-motion: node entries, edge draws, and focus transitions all collapse to instant.

Credits

• Extracted from: algoflashcards (src/lessons/primitives/viz/RecurrenceTreeViz.tsx). The source was a level-as-bars renderer — one horizontal bar per recursion level whose width encoded total work, intended to teach Master-Theorem cases. The library version is a different primitive: an actual call tree, not a work-per-level histogram, because LevelWorkBars already covers the bar story. Reframing the abstraction around nodes (with parentId plus value plus tone) lets the same component show fibonacci, merge-sort, quicksort, expression-tree DP, and post-order completion — the geometric shape of recursion itself.