flex_algo/
binary_search_tree.rs

1use std::fmt::Debug;
2
3/// BinarySearchTree
4/// 
5/// This crate implements a Binary Search Tree data structure with insert, 
6/// preorder traversal, search and validate algorithms.
7/// 
8#[derive(Debug)]
9pub struct BST<T>(Option<Box<BinaryNode<T>>>);
10
11#[derive(Debug)]
12pub struct BinaryNode<T> {
13    data: T,
14    left: BST<T>,
15    right: BST<T>,
16}
17
18impl<T> BinaryNode<T> {
19    pub fn new(data: T) -> Self {
20        BinaryNode {
21            data,
22            left: BST(None),
23            right: BST(None),
24        }
25    }
26}
27
28impl<T> BST<T> {
29    /// Create a new BinarySearchTree
30    /// 
31    /// # Example
32    /// 
33    /// ```
34    /// use flex_algo::BST;
35    /// 
36    /// let mut bst = BST::new();
37    /// bst.insert(3);
38    /// bst.insert(2);
39    /// bst.insert(1);
40    /// 
41    /// ```
42    /// 
43    pub fn new() -> Self {
44      BST(None)
45    }
46}
47
48impl<T> BST<T> 
49where T: PartialOrd + Copy
50{
51    /// Insert into a new BinarySearchTree
52    /// 
53    /// # Example
54    /// 
55    /// ```
56    /// use flex_algo::BST;
57    /// 
58    /// let mut bst = BST::new();
59    /// bst.insert(3);
60    /// bst.insert(2);
61    /// bst.insert(1);
62    /// 
63    /// ```
64    /// 
65    pub fn insert(&mut self, data: T) -> bool {
66        match self.0 {
67            Some(ref mut node) => {
68                if node.data == data {
69                    return false;
70                }
71                if data < node.data {
72                    return node.left.insert(data);
73                } else {
74                    return node.right.insert(data);
75                }
76            }
77            None => {
78                self.0 = Some(Box::new(BinaryNode::new(data)));
79            }
80        }
81        true
82    }
83
84    /// Validate a new BinarySearchTree
85    /// 
86    /// # Example
87    /// 
88    /// ```
89    /// use flex_algo::BST;
90    /// 
91    /// let mut bst = BST::new();
92    /// bst.insert(3);
93    /// bst.insert(2);
94    /// bst.insert(1);
95    /// 
96    /// let is_valid = bst.is_valid(i32::MIN, i32::MAX);
97    /// assert_eq!(is_valid, true);
98    /// 
99    /// ```
100    /// 
101    pub fn is_valid(&self, min: T, max: T) -> bool {
102        if let Some(ref node) = self.0 {
103            if node.data <= min || node.data >= max {
104                return false;
105            }
106            if !node.left.is_valid(min, node.data) {
107                return false;
108            }
109            if !node.right.is_valid(min, max) {
110                return false;
111            }
112        }
113        true
114    }
115
116    /// Search a new BinarySearchTree
117    /// 
118    /// # Example
119    /// 
120    /// ```
121    /// use flex_algo::BST;
122    /// 
123    /// let mut bst = BST::new();
124    /// bst.insert(3);
125    /// bst.insert(2);
126    /// bst.insert(1);
127    /// 
128    /// let none = bst.search(5);
129    /// assert_eq!(none, None);
130    /// 
131    /// let found = bst.search(2);
132    /// assert_eq!(found, Some(2));
133    /// 
134    /// ```
135    /// 
136    pub fn search(&self, data: T) -> Option<T> {
137        if let Some(ref node) = self.0 {
138            if node.data == data {
139                return Some(data);
140            }
141            if data < node.data {
142                return node.left.search(data);
143            } else {
144                return node.right.search(data);
145            }
146        }
147        None
148    }
149}
150
151impl<T: Debug> BST<T> {
152    /// Traversal a new BinarySearchTree preorder
153    /// 
154    /// # Example
155    /// 
156    /// ```
157    /// use flex_algo::BST;
158    /// 
159    /// let mut bst = BST::new();
160    /// bst.insert(3);
161    /// bst.insert(2);
162    /// bst.insert(1);
163    /// 
164    /// bst.print_preorder(0);
165    /// 
166    /// ```
167    /// 
168    pub fn print_preorder(&self, depth: i32) {
169        if let Some(ref node) = self.0 {
170            node.left.print_preorder(depth + 1);
171            let mut space = String::new();
172            for _ in 0..depth {
173                space.push('.');
174            }
175            println!("{}{:?}", space, node.data);
176            node.right.print_preorder(depth + 1);
177        }
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    #[test]
186    fn test_bst_insert() {
187        let mut bst = BST::new();
188        bst.insert(3);
189        bst.insert(2);
190        bst.insert(1);
191        bst.print_preorder(0);
192    }
193
194    #[test]
195    fn test_bst_is_valid() {
196        let mut bst = BST::new();
197        bst.insert(3);
198        bst.insert(2);
199        bst.insert(1);
200        
201        let is_valid = bst.is_valid(i32::MIN, i32::MAX);
202        assert_eq!(is_valid, true);
203    }
204
205    #[test]
206    fn test_bst_search() {
207        let mut bst = BST::new();
208        bst.insert(3);
209        bst.insert(2);
210        bst.insert(1);
211        let none = bst.search(5);
212        assert_eq!(none, None);
213
214        let found = bst.search(2);
215        assert_eq!(found, Some(2));
216    }
217}
flex_algo/binary_search_tree.rs

flex_algo/
binary_search_tree.rs
