BST Insert - Rust DSA

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.

binary search tree Values smaller than a node go left; larger values go right.

Visual walkthrough

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

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 insert(root: &mut Option<Box<Node>>, value: i32) { match root { None => *root = Some(Box::new(Node::new(value))), Some(node) => if value < node.value { insert(&mut node.left, value) } else { insert(&mut node.right, value) } } }
fn main() { let mut root = None; for value in [4, 2, 6, 1, 3, 5, 7] { insert(&mut root, value); } println!("{}", render(&root)); }

                        

Complexity

Time: O(h) per insert
Space: O(n)

Implementation notes

Rust stores each child as Option<Box<Node>>: struct Node { value: i32, left: Option<Box<Node>>, right: Option<Box<Node>> }. None represents an empty child and Some(Box<Node>) owns the subtree.
Node::new(value) creates a leaf with left: None and right: None; insertion allocates with Some(Box::new(Node::new(value))) when it reaches an empty slot.
insert(root: &mut Option<Box<Node>>, value: i32) mutably borrows the slot to update. Matching on root either fills None or recurses into &mut node.left / &mut node.right.
The branch is if value < node.value; duplicates would follow the else branch into the right subtree, though this checked insertion order has no duplicates.
main starts with let mut root = None and inserts [4, 2, 6, 1, 3, 5, 7], mutating the same owned tree rather than returning a new root.
The trace records tree states after each insert: 4, 4(2,_), 4(2,6), 4(2(1,_),6), 4(2(1,3),6), 4(2(1,3),6(5,_)), then 4(2(1,3),6(5,7)).
render(&root) borrows the tree and formats _ for None, leaf values as bare numbers, and interior nodes as value(left,right). println!("{}", ...) prints 4(2(1,3),6(5,7)).
The replay also includes the sorted-insert contrast 1(_,2(_,3(_,4))), showing this ownership model still degrades to height 4 and O(n) cost without rotations.