# TreeTrace and TreeView

> TreeTrace holds the steps of a binary tree.

Page: https://fframes-kit.pages.dev/docs/computer-science/tree-trace-and-tree-view/
Cargo feature: `cs` (`fframes-kit = { version = "..", features = ["cs"] }`)

`TreeTrace` holds the steps of a binary tree. Each `TreeStep` has the nodes (an id, a label
and the ids of the left and right child), the root, the highlighted nodes, the path walked
to them, a found node and a note. Every step is laid out once when the trace is made, with
`layout::tidy_tree`; a node with one child leans it to its side.
`with_layout(TreeLayout::Tree)` lays the steps out again with the `tree` layout of the graph
layouts (`GraphLayout::Tree`): the children are centred under their parent, so a single child
sits straight below it.

- `TreeTrace::bst(&values)` starts a search tree with the values inserted. `insert`, `search`
  and `remove` walk down from the root one node a step, noting which way they go; `remove`
  replaces a node with two children by the smallest node on its right.
- `TreeTrace::max_heap(&values)` and `min_heap` start a heap. `push` adds at the bottom and
  sifts up, `pop` takes the root and sifts the last node down, a compare and a swap a step.
  Nodes keep their values, so swapped nodes trade places.

`TreeView` draws the trace as round nodes `radius` pixels, `spacing` pixels between slots and
`level` pixels between depths. Highlighted nodes light up, the path is outlined, a found node
turns green, nodes slide to their new places (two swapped nodes pass side by side), new ones
drop in and removed ones fade. Gallery scenes: `TreeView` (a search tree: an insert, a search
and a remove), `Heap` (a push and a pop).

Gallery clip of `TreeView`: https://fframes-kit.pages.dev/media/scenes/TreeView-5603e712.mp4

Gallery clip of `Heap`: https://fframes-kit.pages.dev/media/scenes/Heap-f28e1832.mp4

```rust
use fframes_kit::prelude::*;

let bst = TreeTrace::bst(&[50, 30, 70]).insert(40).remove(30).finish();
let last = bst.steps().last().unwrap();
assert_eq!(last.nodes.len(), 3);
assert_eq!(last.note, "40 moves up");

fn tree<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a TreeTrace) -> Svgr<'a> {
    ui.show(TreeView {
        trace: Some(trace),
        step_time: 0.8,
        ..ui.defaults()
    })
}
```

## API

Components are plain structs. Set the fields you need and fill the rest with `..ui.defaults()`: the defaults below come from the current theme (`theme.` values are fields of `Theme`).

### TreeView

A binary tree: round nodes `radius` pixels with their values, `spacing` pixels between neighbouring slots and `level` pixels between depths, centred on `center` (units of `ui.space`). It plays a `TreeTrace`, one step every `step_time` seconds from `delay`: the nodes a step looks at light up, the path to them is outlined, nodes slide to their new places as the tree changes (swapped heap nodes pass each other), new nodes drop in and removed ones fade. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | `Option<&TreeTrace>` | `None` | The recorded steps to play (`TreeTrace`); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.8` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the tree, in units of `ui.space`. |
| `spacing` | `f32` | `100.0` | Pixels between neighbouring node slots in a depth. |
| `level` | `f32` | `120.0` | Pixels between depths. |
| `radius` | `f32` | `30.0` | Radius of a node in pixels. |
| `notes` | `bool` | `true` | Whether the step's note is written under the tree. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the nodes in each state (looked at, moved, found). |
| `edge_color` | `Color` | `theme.colors.muted` | Colour of the edges between nodes. |
| `path_color` | `Color` | `theme.colors.accent` | Colour of the outline of the path to the nodes a step looks at. |
| `value_style` | `TextStyle` | `value_style` | The font of the values in the nodes. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/tree.rs#L603)