Binary Tree in Rust

I am not new to rust. I have dabbled in axum, tonic, bevy and ratatui for some personal and work projects as well. Even then when someone asked me to write a Binary Search Tree(BST) in rust, I got scared. I didn't express this at the time but it kept bugging me inside.

Anyway later on whenever I used to get time I used to ask AI tools to help me teach rust and write a BST specifically. I used Gemini and ChatGPT and both gave solutions as well. I could understand their code but still couldn't understand how they got there. They used Rc, RefCell etc. which I understand theoretically but never understood when and how to use it properly.

After I didn't feel satisfied using AI answers I thought let me just read code. Rust actually provides a BST in standard library, you can find it here. Its very well written and probably the most efficient implementation. I went through it, understood it, but again the same problem its great but there is no explanation of why things are the way they are. Why for example its using 3 structs BinarySearchTree, Node and Tree. I am sure people smarter than me can decipher the reasons but for my average brained self it looks like magic.

Anyway the fear inside me started becoming dread. So I finally gave up and decided to overcome it by actually implementing it. Opened my editor, played some music and sat looking at the screen, the cursor blinking, my mind thinking and my hands printing chars on the screen.

I didn't use all the structs described in the core rust or AI implementations. I wanted to implement the way I used to implement BST when I learned it, basically one Node class with an insert method calling itself recursively. I decided maybe when I am implementing it this way I'll get stuck and then I will understand why these intermediate structs are necessary.

I started with the Node struct:

#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Node>,
    right: Option<Node>,
}

then I decide I wanted to make it generic, so updated:

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

Ord because I want to the generic type to be comparable. Then rust-analyser started complaining about recursive types so I added Box, which basically ensures the value is spawned on the heap and not the stack.

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

The AI implementations always used Rc<RefCell<>> but I decided not to use it until I actually need it. Also reading through the standard library implementation told me that it is possible to do this with Box only. Anyway now its the meat of the program: the insert function. I was absolutely sure that this will destroy me and I'll just close the laptop lid and drop it.I kept writing till I got this:

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

impl<T: Ord> Node<T> {
    fn new(val: T) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, val: T) {
        match self.val.cmp(&val) {
            std::cmp::Ordering::Greater => {
                if let Some(ref mut node) = self.left {
                    node.insert(val);
                } else {
                    self.left = Some(Box::new(Node::new(val)));
                }
            }
            std::cmp::Ordering::Equal => todo!(),
            std::cmp::Ordering::Less => {
                if let Some(ref mut node) = self.right {
                    node.insert(val);
                } else {
                    self.right = Some(Box::new(Node::new(val)));
                }
            }
        }
    }
}

At least I managed to silence the rust-analyser till the point it was not showing any errors in my editor. Still I was not sure it will work, so I wrote the main and used the example in Rust standard lib implementation:

fn main() {
    let mut head = Node::new(5);
    head.insert(7);
    head.insert(3);
    head.insert(4);
    head.insert(8);
    head.insert(6);
    head.insert(1);

    println!("final tree: {:#?}", head);
}

and that I finally ran cargo run -q. I was surprised to see it worked perfectly. I was so astonished that ended up writing this post, just to share my feeling of elation and the confidence I feel. I know its not much but the kind of happiness you get from conquering your fears is unexplainable. I hope this journey also inspires someone to conquer their fears and do something they have been putting off, you never know you might end up solving it in first go or maybe after few iterations.