Return to Answer

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

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 to improve clarity about their arguments: a constructor that creates a BST with one element could be from_value.

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. There's also an Extend trait that you might implement in any of several ways; see the standard library for examples.

You use a number of ref patterns which are not really necessary. 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.

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

This function 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 format string, and gives some other conveniences like .to_string().

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.

It looks like you're using rustfmt, which is great. Also consider putting some 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.

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.

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.

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.

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.

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.

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().

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.

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.

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 format string, and gives some other conveniences like .to_string().