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 serde::Deserialize;
 
#[derive(Debug, Deserialize)]
#[serde(untagged)]

Parsing flexible JSON shapes with serde

deserialization enums json
Intermediate 6 steps
rust 
use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, BufWriter, Lines, Write};

K-way merge of sorted logs in Rust

binary-heap k-way-merge streaming-io
Intermediate 8 steps
javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
rust 
use axum::{
    extract::{Path, State},
    response::sse::{Event, KeepAlive, Sse},
};

Streaming import progress with SSE in Axum

server-sent-events streams watch-channel
Advanced 7 steps
rust 
use std::f64::consts::PI;
 
#[derive(Debug, Clone, Copy)]
pub struct LatLng {

Building geographic bounding boxes in Rust

geospatial value-types option
Intermediate 7 steps
rust 
use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing
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