Exercise: Binary Tree

A binary tree is a tree-type data structure where every node has two children (left and right). We will create a tree where each node stores a value. For a given node N, all nodes in a N’s left subtree contain smaller values, and all nodes in N’s right subtree will contain larger values.

Implement the following types, so that the given tests pass.

Extra Credit: implement an iterator over a binary tree that returns the values in order.

  1. /// A node in the binary tree.
  2. #[derive(Debug)]
  3. struct Node<T: Ord> {
  4.     value: T,
  5.     left: Subtree<T>,
  6.     right: Subtree<T>,
  7. }
  9. /// A possibly-empty subtree.
  10. #[derive(Debug)]
  11. struct Subtree<T: Ord>(Option<Box<Node<T>>>);
  13. /// A container storing a set of values, using a binary tree.
  14. ///
  15. /// If the same value is added multiple times, it is only stored once.
  16. #[derive(Debug)]
  17. pub struct BinaryTree<T: Ord> {
  18.     root: Subtree<T>,
  19. }
  21. impl<T: Ord> BinaryTree<T> {
  22.     fn new() -> Self {
  23.         Self { root: Subtree::new() }
  24.     }
  26.     fn insert(&mut self, value: T) {
  27.         self.root.insert(value);
  28.     }
  30.     fn has(&self, value: &T) -> bool {
  31.         self.root.has(value)
  32.     }
  34.     fn len(&self) -> usize {
  35.         self.root.len()
  36.     }
  37. }
  39. // Implement `new`, `insert`, `len`, and `has` for `Subtree`.
  41. #[cfg(test)]
  42. mod tests {
  43.     use super::*;
  45.     #[test]
  46.     fn len() {
  47.         let mut tree = BinaryTree::new();
  48.         assert_eq!(tree.len(), 0);
  49.         tree.insert(2);
  50.         assert_eq!(tree.len(), 1);
  51.         tree.insert(1);
  52.         assert_eq!(tree.len(), 2);
  53.         tree.insert(2); // not a unique item
  54.         assert_eq!(tree.len(), 2);
  55.     }
  57.     #[test]
  58.     fn has() {
  59.         let mut tree = BinaryTree::new();
  60.         fn check_has(tree: &BinaryTree<i32>, exp: &[bool]) {
  61.             let got: Vec<bool> =
  62.                 (0..exp.len()).map(|i| tree.has(&(i as i32))).collect();
  63.             assert_eq!(&got, exp);
  64.         }
  66.         check_has(&tree, &[false, false, false, false, false]);
  67.         tree.insert(0);
  68.         check_has(&tree, &[true, false, false, false, false]);
  69.         tree.insert(4);
  70.         check_has(&tree, &[true, false, false, false, true]);
  71.         tree.insert(4);
  72.         check_has(&tree, &[true, false, false, false, true]);
  73.         tree.insert(3);
  74.         check_has(&tree, &[true, false, false, true, true]);
  75.     }
  77.     #[test]
  78.     fn unbalanced() {
  79.         let mut tree = BinaryTree::new();
  80.         for i in 0..100 {
  81.             tree.insert(i);
  82.         }
  83.         assert_eq!(tree.len(), 100);
  84.         assert!(tree.has(&50));
  85.     }
  86. }