Solution

1. ```
   use std::cmp::Ordering;
   ```

3. ```
   /// A node in the binary tree.
   ```
4. ```
   #[derive(Debug)]
   ```
5. ```
   struct Node<T: Ord> {
   ```
6. ```
       value: T,
   ```
7. ```
       left: Subtree<T>,
   ```
8. ```
       right: Subtree<T>,
   ```
9. ```
   }
   ```

11. ```
    /// A possibly-empty subtree.
    ```
12. ```
    #[derive(Debug)]
    ```
13. ```
    struct Subtree<T: Ord>(Option<Box<Node<T>>>);
    ```

15. ```
    /// A container storing a set of values, using a binary tree.
    ```
16. ```
    ///
    ```
17. ```
    /// If the same value is added multiple times, it is only stored once.
    ```
18. ```
    #[derive(Debug)]
    ```
19. ```
    pub struct BinaryTree<T: Ord> {
    ```
20. ```
        root: Subtree<T>,
    ```
21. ```
    }
    ```

23. ```
    impl<T: Ord> BinaryTree<T> {
    ```
24. ```
        fn new() -> Self {
    ```
25. ```
            Self { root: Subtree::new() }
    ```
26. ```
        }
    ```

28. ```
        fn insert(&mut self, value: T) {
    ```
29. ```
            self.root.insert(value);
    ```
30. ```
        }
    ```

32. ```
        fn has(&self, value: &T) -> bool {
    ```
33. ```
            self.root.has(value)
    ```
34. ```
        }
    ```

36. ```
        fn len(&self) -> usize {
    ```
37. ```
            self.root.len()
    ```
38. ```
        }
    ```
39. ```
    }
    ```

41. ```
    impl<T: Ord> Subtree<T> {
    ```
42. ```
        fn new() -> Self {
    ```
43. ```
            Self(None)
    ```
44. ```
        }
    ```

46. ```
        fn insert(&mut self, value: T) {
    ```
47. ```
            match &mut self.0 {
    ```
48. ```
                None => self.0 = Some(Box::new(Node::new(value))),
    ```
49. ```
                Some(n) => match value.cmp(&n.value) {
    ```
50. ```
                    Ordering::Less => n.left.insert(value),
    ```
51. ```
                    Ordering::Equal => {}
    ```
52. ```
                    Ordering::Greater => n.right.insert(value),
    ```
53. ```
                },
    ```
54. ```
            }
    ```
55. ```
        }
    ```

57. ```
        fn has(&self, value: &T) -> bool {
    ```
58. ```
            match &self.0 {
    ```
59. ```
                None => false,
    ```
60. ```
                Some(n) => match value.cmp(&n.value) {
    ```
61. ```
                    Ordering::Less => n.left.has(value),
    ```
62. ```
                    Ordering::Equal => true,
    ```
63. ```
                    Ordering::Greater => n.right.has(value),
    ```
64. ```
                },
    ```
65. ```
            }
    ```
66. ```
        }
    ```

68. ```
        fn len(&self) -> usize {
    ```
69. ```
            match &self.0 {
    ```
70. ```
                None => 0,
    ```
71. ```
                Some(n) => 1 + n.left.len() + n.right.len(),
    ```
72. ```
            }
    ```
73. ```
        }
    ```
74. ```
    }
    ```

76. ```
    impl<T: Ord> Node<T> {
    ```
77. ```
        fn new(value: T) -> Self {
    ```
78. ```
            Self { value, left: Subtree::new(), right: Subtree::new() }
    ```
79. ```
        }
    ```
80. ```
    }
    ```

82. ```
    fn main() {
    ```
83. ```
        let mut tree = BinaryTree::new();
    ```
84. ```
        tree.insert("foo");
    ```
85. ```
        assert_eq!(tree.len(), 1);
    ```
86. ```
        tree.insert("bar");
    ```
87. ```
        assert!(tree.has(&"foo"));
    ```
88. ```
    }
    ```

90. ```
    #[cfg(test)]
    ```
91. ```
    mod tests {
    ```
92. ```
        use super::*;
    ```

94. ```
        #[test]
    ```
95. ```
        fn len() {
    ```
96. ```
            let mut tree = BinaryTree::new();
    ```
97. ```
            assert_eq!(tree.len(), 0);
    ```
98. ```
            tree.insert(2);
    ```
99. ```
            assert_eq!(tree.len(), 1);
    ```
100. ```
             tree.insert(1);
     ```
101. ```
             assert_eq!(tree.len(), 2);
     ```
102. ```
             tree.insert(2); // not a unique item
     ```
103. ```
             assert_eq!(tree.len(), 2);
     ```
104. ```
         }
     ```

106. ```
         #[test]
     ```
107. ```
         fn has() {
     ```
108. ```
             let mut tree = BinaryTree::new();
     ```
109. ```
             fn check_has(tree: &BinaryTree<i32>, exp: &[bool]) {
     ```
110. ```
                 let got: Vec<bool> =
     ```
111. ```
                     (0..exp.len()).map(|i| tree.has(&(i as i32))).collect();
     ```
112. ```
                 assert_eq!(&got, exp);
     ```
113. ```
             }
     ```

115. ```
             check_has(&tree, &[false, false, false, false, false]);
     ```
116. ```
             tree.insert(0);
     ```
117. ```
             check_has(&tree, &[true, false, false, false, false]);
     ```
118. ```
             tree.insert(4);
     ```
119. ```
             check_has(&tree, &[true, false, false, false, true]);
     ```
120. ```
             tree.insert(4);
     ```
121. ```
             check_has(&tree, &[true, false, false, false, true]);
     ```
122. ```
             tree.insert(3);
     ```
123. ```
             check_has(&tree, &[true, false, false, true, true]);
     ```
124. ```
         }
     ```

126. ```
         #[test]
     ```
127. ```
         fn unbalanced() {
     ```
128. ```
             let mut tree = BinaryTree::new();
     ```
129. ```
             for i in 0..100 {
     ```
130. ```
                 tree.insert(i);
     ```
131. ```
             }
     ```
132. ```
             assert_eq!(tree.len(), 100);
     ```
133. ```
             assert!(tree.has(&50));
     ```
134. ```
         }
     ```
135. ```
     }
     ```