Question

How to parse a table into a binary tree in Rust

Answer 1

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

/*
    Parse a table of (id, name, parent_id) into a binary tree using
    the Left‑Child / Right‑Sibling representation.

    Why this representation?
    - The table describes a general tree (each node can have many children).
    - A binary tree requires each node to have at most two pointers.
    - left  -> first child
    - right -> next sibling

    This preserves the full structure while staying inside a binary tree model.
*/

type NodeRef = Rc<RefCell<Node>>;

#[derive(Debug)]
struct Node {
    id: i32,
    name: String,
    left: Option<NodeRef>,   // first child
    right: Option<NodeRef>,  // next sibling
}

impl Node {
    fn new(id: i32, name: &str) -> Self {
        Self {
            id,
            name: name.to_string(),
            left: None,
            right: None,
        }
    }
}

/* -------------------- Print Tree -------------------- */

fn print_tree(node: Option<NodeRef>, depth: usize) {
    let Some(n_rc) = node else { return };
    let n = n_rc.borrow();

    // Print ROOT on its own line
    if depth == 0 {
        println!("ROOT");
    }

    // Indent the node itself
    let indent = "  ".repeat(depth + 1);
    println!("{indent}{:02} - {}", n.id, n.name);

    // first child
    print_tree(n.left.clone(), depth + 1);

    // next sibling (another top-level node)
    if depth == 0 {
        print_tree(n.right.clone(), 0); // restart ROOT
    } else {
        print_tree(n.right.clone(), depth);
    }
}

/* ------------------------------------------------------------
   Build the tree using Left‑Child / Right‑Sibling representation
   ------------------------------------------------------------ */

#[derive(Clone)]
struct Row {
    id: i32,
    name: &'static str,
    parent_id: i32,
}

fn build_tree(table: &[Row]) -> Option<NodeRef> {
    // Create nodes
    let mut nodes: HashMap<i32, NodeRef> = HashMap::new();
    for row in table {
        nodes.insert(row.id, Rc::new(RefCell::new(Node::new(row.id, row.name))));
    }

    let mut root: Option<NodeRef> = None;

    // Attach children and siblings
    for row in table {
        let id = row.id;
        let parent_id = row.parent_id;

        let current = nodes.get(&id).cloned().expect("node must exist");

        if parent_id == 0 {
            // top-level node → sibling chain under root
            match root {
                None => root = Some(current),
                Some(ref r) => {
                    let mut p = r.clone();
                    loop {
                        let right_opt = p.borrow().right.clone();
                        match right_opt {
                            Some(next) => p = next,
                            None => {
                                p.borrow_mut().right = Some(current.clone());
                                break;
                            }
                        }
                    }
                }
            }
        } else {
            let parent = nodes
                .get(&parent_id)
                .cloned()
                .expect("parent must exist");

            let mut p = parent.clone();
            let mut parent_borrow = p.borrow_mut();

            // attach as first child or next sibling
            match parent_borrow.left.clone() {
                None => {
                    parent_borrow.left = Some(current.clone());
                }
                Some(first_child) => {
                    drop(parent_borrow); // release borrow before reusing p
                    p = first_child;
                    loop {
                        let right_opt = p.borrow().right.clone();
                        match right_opt {
                            Some(next) => p = next,
                            None => {
                                p.borrow_mut().right = Some(current.clone());
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    root
}

/* -------------------- Main -------------------- */

fn main() {
    // Example table
    let table = vec![
        Row { id: 1,  name: "Node 1",        parent_id: 0 },
        Row { id: 2,  name: "Node 1.1",      parent_id: 1 },
        Row { id: 3,  name: "Node 2",        parent_id: 0 },
        Row { id: 4,  name: "Node 1.1.1",    parent_id: 2 },
        Row { id: 5,  name: "Node 2.1",      parent_id: 3 },
        Row { id: 6,  name: "Node 2.3.1",    parent_id: 3 },
        Row { id: 7,  name: "Node 1.2",      parent_id: 1 },
        Row { id: 8,  name: "Node 1.3",      parent_id: 1 },
        Row { id: 9,  name: "Node 1.3.1",    parent_id: 8 },
        Row { id: 10, name: "Node 2.4",      parent_id: 3 },
        Row { id: 11, name: "Node 2.1.1",    parent_id: 5 },
        Row { id: 12, name: "Node 2.1.1.6",  parent_id: 11 },
    ];

    let root = build_tree(&table);

    print_tree(root, 0);
}


/*
run:

ROOT
  01 - Node 1
    02 - Node 1.1
      04 - Node 1.1.1
    07 - Node 1.2
    08 - Node 1.3
      09 - Node 1.3.1
ROOT
  03 - Node 2
    05 - Node 2.1
      11 - Node 2.1.1
        12 - Node 2.1.1.6
    06 - Node 2.3.1
    10 - Node 2.4

*/

 

70+ SQL courses for beginners and professionals