Lab: Binary Search Tree

In today's lab, your goal is to gain experience building data structures in Rust. You'll achieve this by extending the binary search tree that we started working on in lecture. Start with either your main.rs or the one we wrote together.

Len

Add a method len to the tree that returns the number of values in the tree as a usize. Empty sentinel nodes don't count as values. This method doesn't require any particular type constraints on T, so define it in a separate impl block that applies to any T. The one we wrote together only applies to T that satisfies the PartialOrd trait. PartialOrd is not necessary for counting nodes.

Test that it works in the main function.

Print

Add a method named print to the tree that prints its elements in order, one per line. Perform an in-order traversal.

This method should only be available for trees whose generic type implements the Display trait. The Display trait means that a value can be printed with a {} placeholder in a format string. Again, don't augment any existing impl block. The existing blocks have different type constraints on T. Instead make a new block with the desired constraints.

Test that it works in the main function.

Between

Add a method named between to the tree. It accepts two parameters: a reference to a RangeInclusive holding a low value and a high value, and a reference to a mutable Vec. It fills the Vec with all elements within the given range, in order.

This method should only be available for trees whose generic type implements both the PartialOrd and Copy traits. The Copy trait means that the compiler will implicitly make a copy of a value so that the Tree won't lose ownership when we put an item in the Vec.

Trees have a recursive structure, and your solution should reflect that. Be careful, however, as recursion easily becomes more expensive than iterative solutions. Follow this advice to keep the recursion fast:

• Only recurse on children that might actually contribute elements. If the range is 40-50 and you reach a node with value 35, what should happen? What if the value is 55? What if the value is 45?
• If each recursive call returns a Vec, you will have to do a lot of expensive merging. Avoid merging by accumulating the result up in the mutable Vec parameter instead of returning a Vec.

Test that it works in the main function.

Submit

To receive credit for this lab, you must submit your modified main.rs file on Canvas by the noon on Monday after break. Late labs or forgot-to-submits are not accepted because Monday at noon is when your instructor has time to grade.