rust 36 lines · 6 steps

Building a tree from flat parent-id rows in Rust

Turn a flat list of rows with parent pointers into a nested forest using a lookup map and recursion.

Explained by highlit
Intermediate recursion hashmap tree-building iterators grouping
1use std::collections::HashMap;
2 
3#[derive(Debug, Clone)]
4struct Row {
5 id: u64,
6 parent_id: Option<u64>,
7 name: String,
8}
9 
10#[derive(Debug)]
11struct Node {
12 id: u64,
13 name: String,
14 children: Vec<Node>,
15}
16 
17fn build_forest(rows: Vec<Row>) -> Vec<Node> {
18 let mut children_of: HashMap<Option<u64>, Vec<Row>> = HashMap::new();
19 for row in rows {
20 children_of.entry(row.parent_id).or_default().push(row);
21 }
22 build_level(None, &children_of)
23}
24 
25fn build_level(parent: Option<u64>, children_of: &HashMap<Option<u64>, Vec<Row>>) -> Vec<Node> {
26 children_of
27 .get(&parent)
28 .into_iter()
29 .flatten()
30 .map(|row| Node {
31 id: row.id,
32 name: row.name.clone(),
33 children: build_level(Some(row.id), children_of),
34 })
35 .collect()
36}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Grouping rows by parent once turns an O(n^2) tree build into a series of cheap map lookups.
  2. 2Using Option<u64> as the map key lets roots (None parent) share the same grouping logic as any other node.
  3. 3into_iter().flatten() cleanly handles a missing key as an empty child list without special-casing.

Related explainers

rust 
use std::cmp::Ordering;
 
pub struct PrefixIndex {
    entries: Vec<String>,

Prefix search with binary partitioning in Rust

binary-search sorting case-insensitive
Intermediate 7 steps
rust 
use std::cmp::Ordering;
use std::str::FromStr;
 
#[derive(Debug, Clone, PartialEq, Eq)]

Parsing and ordering semantic versions in Rust

parsing trait-implementation ordering
Intermediate 8 steps
rust 
use axum::{
    extract::State,
    routing::{get, post, MethodRouter},
    Json, Router,

Self-documenting routes in Axum

builder-pattern closures shared-state
Intermediate 8 steps
rust 
use std::collections::HashMap;
use std::fs::File;
use std::io::{self, BufRead, BufReader};
use std::path::Path;

Parsing INI files in Rust

parsing file-io hashmap
Intermediate 9 steps
rust 
use axum::{
    extract::{Path, Query},
    http::Uri,
    response::{IntoResponse, Redirect},

Building HTTP redirect handlers in Axum

redirects extractors url-handling
Intermediate 7 steps
rust 
use axum::{
    body::Body,
    extract::MatchedPath,
    http::{Request, StatusCode},

An admin route guard in Axum middleware

middleware authorization request-extensions
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Building a tree from flat parent-id rows in Rust — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code