bs.rs

use std::cmp::Ordering;

pub mod printer;

pub struct BinaryTree<T> {
    root: Option<Node<T>>,
}

impl<T: Ord> BinaryTree<T> {
    /// Creates a new binary tree.
    pub fn new() -> Self {
        Self { root: None }
    }

    /// Creates a new binary tree.
    ///
    /// Returns an `Err` with the value if it already exists in the tree.
    pub fn insert(&mut self, value: T) -> Result<(), T> {
        match self.root.as_mut() {
            Some(root) => root.insert(value),
            None => {
                self.root = Some(Node::new(value));
                Ok(())
            }
        }
    }
}

struct Node<T> {
    value: T,
    left: Box<Option<Node<T>>>,
    right: Box<Option<Node<T>>>,
}

impl<T: Ord> Node<T> {
    /// Creates a new node.
    fn new(value: T) -> Self {
        Self {
            value,
            left: Box::new(None),
            right: Box::new(None),
        }
    }

    /// Creates a new binary tree.
    ///
    /// Returns an `Err` with the value if it already exists in the tree.
    fn insert(&mut self, value: T) -> Result<(), T> {
        match value.cmp(&self.value) {
            Ordering::Less => match self.left.as_mut() {
                Some(node) => node.insert(value),
                None => {
                    self.left = Some(Self::new(value)).into();
                    Ok(())
                }
            },
            Ordering::Greater => match self.right.as_mut() {
                Some(node) => node.insert(value),
                None => {
                    self.right = Some(Self::new(value)).into();
                    Ok(())
                }
            },
            Ordering::Equal => Err(value),
        }
    }
}