Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Rust DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.rs

use std::collections::VecDeque;
struct Node { value: i32, left: Option<Box<Node>>, right: Option<Box<Node>> }
impl Node {
    fn new(value: i32) -> Self { Self { value, left: None, right: None } }
    fn with(value: i32, left: Node, right: Node) -> Self {
        Self { value, left: Some(Box::new(left)), right: Some(Box::new(right)) }
    }
}
fn render(node: &Option<Box<Node>>) -> String {
    match node {
        None => "_".to_string(),
        Some(n) => {
            if n.left.is_none() && n.right.is_none() { n.value.to_string() }
            else { format!("{}({},{})", n.value, render(&n.left), render(&n.right)) }
        }
    }
}
fn sample_tree() -> Option<Box<Node>> {
    Some(Box::new(Node::with(4, Node::with(2, Node::new(1), Node::new(3)), Node::with(6, Node::new(5), Node::new(7)))))
}
fn list_string(values: &[i32]) -> String {
    format!("[{}]", values.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(", "))
}
fn main() { let root = sample_tree(); println!("{}", render(&root)); }

Complexity

Time: O(n)
Space: O(n)

Implementation notes

Rust stores child links as Option<Box<Node>>: struct Node { value: i32, left: Option<Box<Node>>, right: Option<Box<Node>> }. None is an empty child and Some(Box<Node>) owns a subtree.
Node::new(value) builds a leaf with both children set to None. Node::with(value, left, right) takes owned child Node values and boxes them into Some(Box::new(...)).
sample_tree() -> Option<Box<Node>> wraps the root in Some(Box::new(...)) and assembles 4(2(1,3),6(5,7)) with nested constructor calls, not later mutable child assignments.
The trace records construction bottom-up: 1, 3, then 2(1,3); 5, 7, then 6(5,7); finally root 4(2(1,3),6(5,7)).
render(&root) borrows the owned tree, formats None as _, leaves as their value, and interior nodes as value(left,right).
println!("{}", render(&root)) uses display formatting and prints 4(2(1,3),6(5,7)).
The file includes shared VecDeque and list_string scaffolding, but this checked lesson does not use them. There is no imbalance/degradation trace in this tree-build page.

node links A node stores one value plus references to its left and right children.