Best way in Rust to count leaves in a binary search tree?

user_14456587 0
Viewed 103

I'm developing a basic implementation of a binary search tree in Rust. I was creating a method for counting leaves, but ran into some very strange looking code to get it to work. I wanted to clarify if the way I did it is:

  1. Considered appropriate by Rust standards/convention
  2. Efficient

I'm using an enum that differentiates between a node or nothing being present:

pub enum BST<T: Ord> {
    Node {
        value: T, // template with type T
        left: Box<BST<T>>,
        right: Box<BST<T>>,
    },
    Empty,
}

Now, count_leaves(&self) is first checking if the provided type is either a Node or Empty. If it's Empty, I can just return 0, but if it's a valid Node then I need to check if the left and right children are Empty. If so, then I can return a 1 because I'm at a leaf.

pub fn count_leaves(&self) -> u32 {
    match self {
        BST::Node {
            value: _,
            ref left,
            ref right,
        } => {
            match (&**left, &**right) {
                (BST::Empty, BST::Empty) => 1,
                _ => {
                    left.count_leaves() + right.count_leaves()
                }
            }
        },
        BST::Empty => 0
    }
}

So, to check if both left and right are BST::Empty, I wanted to use a tuple! But in doing so, Rust tries to move both left and right into the tuple. Since my type BST<T> does not implement the Copy trait, this is not possible. Also, since left and right are both boxes and borrowed, something simply like this is not possible:

match (left, right) {
    BST::Empty => {},
    _ => {}
}

In order to use this tuple, it looks like I need to first dereference the borrowed box using *, then dereference that box again into its type using a second *, and then finally borrow using & to avoid a move. This gives the weird looking (&**left, &**right).

From my testing this works, but I thought it looked really strange. Should I rewrite this in a more readable way (if there is one)?

I've considered using Option<> instead of the enum with the Node and Empty, but I wasn't sure if that would lead to anything more readable or more efficient.

Thanks!

EDIT:

Just wanted to clarify that when I say leaves I mean a node in the tree with no children, not a non-empty node.

rust binary-search-tree
1 Answers

You're just overthinking it. You already have a base case for when a node is empty so you don't need both matches. When possible you want to ignore the boxes in favor of implicitly using Deref to perform operations on them.

pub fn count_leaves(&self) -> u32 {
    match self {
        BST::Node { left, right, .. } => 1 + left.count_leaves() + right.count_leaves(),
        BST::Empty => 0,
    }
}

By manually checking if both sides are empty before calling count_leaves on both sides, you might actually be decreasing performance. A recursive function call (or any function call really) can be very cheap since your code is already at the processor. However, it takes (a very tiny) time for a processor to read a value from a pointer so ideally you only needs to do it once per value. However the compiler is made of eldritch sorcery so it will probably figure out the best way to optimize your code either way. Another option which may help is to add an #[inline] hint to the function to ask the compiler to unroll the recursive call one or more times if it thinks it would be helpful for performance.

You may find it helpful to change the structure of your BST. By making your tree an enum, then it needs to be matched every time you perform any operation on it.

pub struct BST<T> {
    left: Option<Box<BST<T>>>,
    right: Option<Box<BST<T>>>,
    data: T,
}

impl<T> BST<T> {
    pub fn new_root(data: T) -> Self {
        BST {
            left: None,
            right: None,
            data,
        }
    }

    pub fn count_leaves(&self) -> u64 {
        let left_leaves = self.left.as_ref().map_or(0, |x| x.count_leaves());
        let right_leaves = self.right.as_ref().map_or(0, |x| x.count_leaves());
        left_leaves + right_leaves + 1
    }
}

impl<T: Ord> BST<T> {
    pub fn insert(&mut self, data: T) {
        let side = match self.data.cmp(&data) {
            Ordering::Less | Ordering::Equal => &mut self.left,
            Ordering::Greater => &mut self.right,
        };
        
        if let Some(node) = side {
            node.insert(data);
        } else {
            *side = Some(Box::new(Self::new_root(data)));
        }
    }
}

Now this works well, but it also introduces a new problem that I'm guessing you were attempting to avoid with your solution. You can't create an empty BST<T>. This may make initializing your program difficult. We can fix this by using a small wrapper struct (Ex: pub struct BinarySearchTree<T>(Option<BST<T>>)). This is also what std::collections::LinkedList does. You may also be surprised to learn that this cuts our memory footprint in half compared to the original post. This is caused by Empty requiring just as much space as Node. So this means we need to allocate the entire next layer of the tree even though we don't use it.

user_59876690
Related