5
\$\begingroup\$

I am looking for some feedback on my implementation of binary search tree in rust and I would appreciate someone taking the time to go through it and suggest any improvements or corrections as they see fit. More specifically I am concerned about if I should have Clone derives in the BST and Node structs since I am not using them here.

#![allow(unused)]

use std::fmt::Debug;
fn main() {
    let mut bst = BST::new(3_i32);
    bst.append(4);
    bst.append(1);
    bst.append(12);
    bst.display();
}
#[derive(Debug)]
pub struct BST<T> {
    root: Box<Node<T>>,
}
#[derive(Clone, Debug)]
pub struct Node<T> {
    val: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> BST<T>
where
    T: PartialOrd + Debug + Clone,
{
    pub fn new(val: T) -> Self {
        let root = Box::new(Node {
            val,
            left: None,
            right: None,
        });
        Self { root }
    }
    pub fn append(&mut self, new_val: T) {
        let new_node = Box::new(Node {
            val: new_val,
            left: None,
            right: None,
        });
        Self::push_node(new_node, &mut self.root);
    }
    // Private and recursive method
    // recursively search through every node until the value is inserted
    fn push_node(new_node: Box<Node<T>>, current_node: &mut Box<Node<T>>) {
        let ref new_val = new_node.val;
        let ref current_val = current_node.val;
        if *current_val <= *new_val {
            if let Some(ref mut left) = current_node.left {
                Self::push_node(new_node, left);
            } else {
                current_node.left = Some(new_node);
            }
        } else if *current_val > *new_val {
            if let Some(ref mut right) = current_node.right {
                Self::push_node(new_node, right);
            } else {
                current_node.right = Some(new_node);
            }
        }
    }

    fn display(&self) {
        println!("{:#?}", self);
    }
}
\$\endgroup\$
3
\$\begingroup\$

This looks good for a first project. Most of the review to follow ranges from debatable to nitpicky.

Representation

It's unusual that BST can't represent an empty tree because it always has at least one Node in it. Most data structures have no problem representing emptiness. You use Option<_> inside Node; there's no apparent reason not to use it in BST as well. Doing this also lets you simplify push_node by making the non-recursive case – an empty Option – the same between left and right trees.

If you have not already, please read Learning Rust With Entirely Too Many Linked Lists. This short book will cover a lot of mistakes you may make or have already made when trying to create data structures in Rust.

Traits

What traits to implement is really up to you. That said, it's a good idea to implement Clone, Debug and Default for almost all types. Clone and Debug can be #[derive]d; Default needs its own impl because the derived bounds on T are too conservative.

Eq, Hash, Ord, PartialEq, and PartialOrd also seem to make sense here and all can be #[derive]d.

For a challenge, implement FromIterator and IntoIterator, which are as close as Rust has to a "collections" API. Again, the too-many-lists book will help you here.

Construction

By convention (C-COMMON-TRAITS), new (if it exists) should usually take no arguments and do the same thing as the Default trait (if implemented). If you implement Default on BST, you can write new by just calling Default::default(). Additional constructors should be named descriptively: a constructor that creates a BST with one element might be called from_value.

impl bounds

In general, only write bounds for the functions where they are used. new and append clearly don't need T: Debug and none of them need T: Clone. You can either put the specific bounds on the functions themselves, or split the functions among impl blocks with different bounds.

PartialOrd vs. Ord

Partial ordering is not a strong enough guarantee for a binary search tree: if items cannot be ordered relative to each other, they can't be reliably inserted or retrieved from the tree. Therefore the traversal algorithms should require T: Ord, not T: PartialOrd.

append

In Rust, append usually means a method of the signature fn(&mut self, other: &mut Self); that is, one that cannibalizes another data structure of the same type. (As far as I know, this meaning is unique to Rust.) The function you call append would probably be called insert (as in HashSet, for example). There's also an Extend trait that you might implement in any of several ways; see the standard library for examples.

ref patterns

You use a number of ref patterns that are not really necessary. Some people dislike all ref patterns. I don't personally have an issue with them in an if let or match, even though they technically aren't needed due to the questionably named "pattern ergonomics" feature (you can use if let Some(f) = &mut foo instead of if let Some(ref mut f) = foo; the Some becomes transparent). However, I recommend against using ref in a trivial case like let new_val = &new_node.val.

if let and match

If you have an if let with an else clause, consider turning it into a match, especially if one or both branches are short.

std::cmp::Ordering

Instead of an if chain where you test separately a <= b and a > b, call a.cmp(&b) (or T::cmp(&a, &b)) and match on the Ordering. This reduces the chance of accidentally writing a comparison backwards or forgetting a case. Note also that in the original version of push_node, if the values were incomparable, the new_node would have been simply lost. Using Ord instead of PartialOrd means this is not possible.

BST

Conventional capitalization is Bst (C-CASE).

display

This method is not useful. Besides having a misleading name (since it uses the Debug trait, not Display), it's both less obvious in its function and less flexible than simply writing println!("{:#?}", bst) (or even shorter: dbg!(bst)). There's no particular reason to have a dedicated method for it.

If you mean to have a text representation of a tree for display purposes, but not necessarily the same as the Debug implementation, that's precisely what the Display trait is for. Implementing Display will make Bst work in any formatting macro (format!, write!, etc.), and gives some other conveniences like .to_string().

pub struct Node<T>

There is probably not a good reason for Node to be pub. It is dubious for external code to be mucking about with "raw" nodes. If you intend to provide an API that allows back-and-forth traversal, or insertion-at-a-point, consider using a new struct (a cursor) for that so that you can more easily make changes to the internal Node type without changing the API.

Whitespace

It looks like you're using rustfmt, which is great. Also consider putting empty lines between items (functions, structs, impl blocks) to create whitespace around the important program elements and make the code more pleasant to read, in the same way that paragraphs and section headings have whitespace around them in written text.

#[allow(unused)]

allow(unused) might be OK when prototyping so that you don't lose track of important warnings among the trivial ones. But once you have something that is relatively complete, you should not continue to hide unused code warnings: those are bugs waiting to happen.

Even while prototyping, I recommend using allow(dead_code) (which just allows unused non-pub items) instead of the more general allow(unused), which hides a lot more warnings, many of which are helpful at any stage of development.

Code with all suggested changes

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the valuable feedback. I'll keep these tips in mind. \$\endgroup\$
    – RoboT
    Sep 10 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.