Informational code for implementing a binary search tree in Rust.

binary_tree.rs

#![deny(clippy::all, clippy::pedantic)]

use std::cmp::Ordering;

/// A binary search tree.
#[derive(Debug)]
pub enum BinaryTree<T> {
    /// Leaf node
    Leaf,

    /// Internal node, has data and two children
    Tree(T, Box<BinaryTree<T>>, Box<BinaryTree<T>>),
}

impl<T> BinaryTree<T> {
    /// Create an empty tree.
    #[must_use]
    pub fn new() -> Self {
        Self::Leaf
    }
}

impl<T: Ord> BinaryTree<T> {
    /// Insert a new element into this tree.
    ///
    /// There is no rebalancing going on, so the tree will only be useful if the elements are
    /// expected to come from a random sequence. Duplicates are ignored.
    pub fn insert(&mut self, elem: T) {
        match self {
            Self::Leaf => *self = Self::Tree(elem, Box::new(Self::Leaf), Box::new(Self::Leaf)),
            Self::Tree(val, left, right) => match elem.cmp(val) {
                Ordering::Less => left.insert(elem),
                Ordering::Equal => (),
                Ordering::Greater => right.insert(elem),
            },
        }
    }

    /// Search for an element in the tree.
    pub fn search(&self, elem: &T) -> bool {
        match self {
            Self::Leaf => false,
            Self::Tree(val, left, right) => match elem.cmp(val) {
                Ordering::Less => left.search(elem),
                Ordering::Equal => true,
                Ordering::Greater => right.search(elem),
            },
        }
    }
}

impl<T> Default for BinaryTree<T> {
    fn default() -> Self {
        Self::Leaf
    }
}

#[cfg(test)]
mod tests {
    use super::BinaryTree;

    #[test]
    fn test_tree() {
        let mut tree = BinaryTree::new();

        tree.insert(42);
        tree.insert(9);
        tree.insert(-99);
        tree.insert(0);
        tree.insert(23);
        dbg!(&tree);

        assert!(tree.search(&42));
        assert!(tree.search(&9));
        assert!(tree.search(&-99));
        assert!(tree.search(&0));
        assert!(tree.search(&23));

        assert!(!tree.search(&1));
        assert!(!tree.search(&7));
        assert!(!tree.search(&100));
        assert!(!tree.search(&-88));
    }
}