Binary Trees & BST

Binary trees are hierarchical data structures where each node has at most two children: left and right. Binary Search Trees (BST) maintain the invariant that left children are smaller and right children are larger than the parent.

In Rust, trees present unique ownership challenges because nodes need to reference their children, and sometimes their parents.

Implementing trees in Rust requires careful consideration of:

• Ownership: Who owns each node? The parent? A central allocator?
• Mutability: How do we modify tree structure while traversing?
• Self-references: Parent pointers create cycles that Rc/Arc alone can't handle

use std::cmp::Ordering;

/// A Binary Search Tree using Box for child ownership
#[derive(Debug)]
pub struct BinarySearchTree<T> {
    root: Option<Box<Node<T>>>,
}

#[derive(Debug)]
struct Node<T> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T: Ord> BinarySearchTree<T> {
    pub fn new() -> Self {
        BinarySearchTree { root: None }
    }

    pub fn insert(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            left: None,
            right: None,
        });

        match &mut self.root {
            None => self.root = Some(new_node),
            Some(root) => Self::insert_recursive(root, new_node),
        }
    }

    fn insert_recursive(current: &mut Box<Node<T>>, new_node: Box<Node<T>>) {
        match new_node.value.cmp(&current.value) {
            Ordering::Less => match &mut current.left {
                None => current.left = Some(new_node),
                Some(left) => Self::insert_recursive(left, new_node),
            },
            Ordering::Greater | Ordering::Equal => match &mut current.right {
                None => current.right = Some(new_node),
                Some(right) => Self::insert_recursive(right, new_node),
            },
        }
    }

    pub fn contains(&self, value: &T) -> bool {
        Self::search_recursive(&self.root, value)
    }

    fn search_recursive(node: &Option<Box<Node<T>>>, value: &T) -> bool {
        match node {
            None => false,
            Some(n) => match value.cmp(&n.value) {
                Ordering::Equal => true,
                Ordering::Less => Self::search_recursive(&n.left, value),
                Ordering::Greater => Self::search_recursive(&n.right, value),
            },
        }
    }

    /// In-order traversal: left, root, right
    pub fn in_order(&self) -> Vec<&T> {
        let mut result = Vec::new();
        Self::in_order_recursive(&self.root, &mut result);
        result
    }

    fn in_order_recursive<'a>(node: &'a Option<Box<Node<T>>>, result: &mut Vec<&'a T>) {
        if let Some(n) = node {
            Self::in_order_recursive(&n.left, result);
            result.push(&n.value);
            Self::in_order_recursive(&n.right, result);
        }
    }

    pub fn height(&self) -> usize {
        Self::height_recursive(&self.root)
    }

    fn height_recursive(node: &Option<Box<Node<T>>>) -> usize {
        match node {
            None => 0,
            Some(n) => {
                1 + Self::height_recursive(&n.left)
                    .max(Self::height_recursive(&n.right))
            }
        }
    }
}

impl<T: Ord> Default for BinarySearchTree<T> {
    fn default() -> Self {
        Self::new()
    }
}

// Iterator implementation for in-order traversal
pub struct InOrderIter<'a, T> {
    stack: Vec<&'a Node<T>>,
}

impl<'a, T> Iterator for InOrderIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(node) = self.stack.pop() {
            // We've already gone left, so yield this node
            // then go right
            if let Some(ref right) = node.right {
                // Push right subtree
                let mut current = right.as_ref();
                self.stack.push(current);
                while let Some(ref left) = current.left {
                    current = left.as_ref();
                    self.stack.push(current);
                }
            }
            return Some(&node.value);
        }
        None
    }
}

fn main() {
    let mut bst = BinarySearchTree::new();

    // Insert values
    for value in [5, 3, 7, 1, 4, 6, 8] {
        bst.insert(value);
    }

    // Search
    println!("Contains 4: {}", bst.contains(&4)); // true
    println!("Contains 9: {}", bst.contains(&9)); // false

    // Traversal
    println!("In-order: {:?}", bst.in_order()); // [1, 3, 4, 5, 6, 7, 8]

    // Height
    println!("Height: {}", bst.height()); // 3
}

1. Box>: Provides heap allocation with single ownership - perfect for tree children
2. Option>: Represents optional children (leaf nodes have None)
3. Recursive methods: Natural fit for tree operations, Rust handles tail-call optimization
4. Borrowing for search: We only need &self for read operations

For more complex trees (with parent pointers or frequent modifications), consider arena allocation:

use std::cell::RefCell;

pub struct Arena<T> {
    nodes: RefCell<Vec<Node<T>>>,
}

#[derive(Clone, Copy)]
pub struct NodeId(usize);

struct Node<T> {
    value: T,
    left: Option<NodeId>,
    right: Option<NodeId>,
    parent: Option<NodeId>, // Now safe!
}

impl<T> Arena<T> {
    pub fn new() -> Self {
        Arena {
            nodes: RefCell::new(Vec::new()),
        }
    }

    pub fn alloc(&self, value: T) -> NodeId {
        let mut nodes = self.nodes.borrow_mut();
        let id = NodeId(nodes.len());
        nodes.push(Node {
            value,
            left: None,
            right: None,
            parent: None,
        });
        id
    }

    pub fn get(&self, id: NodeId) -> std::cell::Ref<'_, Node<T>> {
        std::cell::Ref::map(self.nodes.borrow(), |nodes| &nodes[id.0])
    }
}

| Approach | Use When |

|----------|----------|

| Box | Simple trees, no parent pointers, single ownership |

| Rc> | Shared ownership needed, interior mutability |

| Arena allocation | Complex graphs, parent pointers, performance-critical |

| petgraph crate | General graphs, need algorithms like Dijkstra |

• Compilers: Abstract Syntax Trees (AST) for parsing
• Databases: B-trees for indexing
• File Systems: Directory structures
• Game engines: Scene graphs, spatial partitioning

1. Implement delete for the BST
2. Add a min() and max() method
3. Implement level-order (breadth-first) traversal
4. Create a balanced tree (AVL or Red-Black)