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. }