Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

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)); }

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.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

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

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

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

Final BST after 5 is present under 6.4261357

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.
binary search tree Values smaller than a node go left; larger values go right.