flex_algo/
binary_tree.rs

1use std::fmt::{Debug, Display, Formatter, Result};
2
3/// BinaryTree
4/// 
5/// This crate implements a BinaryTree data structure with depth,
6/// level order, left/right side view, build a complete tree with count nodes algorithms.
7/// 
8#[derive(Debug)]
9pub struct BinaryTree<T>(Option<Box<BinaryNode<T>>>);
10
11#[derive(Debug)]
12pub struct BinaryNode<T> {
13    data: T,
14    left: BinaryTree<T>,
15    right: BinaryTree<T>,
16}
17
18impl<T> BinaryNode<T> {
19    pub fn new(data: T) -> Self {
20        BinaryNode {
21            data,
22            left: BinaryTree(None),
23            right: BinaryTree(None),
24        }
25    }
26}
27
28impl<T> BinaryTree<T> 
29where T: Copy + Debug + 'static
30{
31    /// Create a new BinaryTree
32    /// 
33    /// # Example
34    /// 
35    /// ```
36    /// use flex_algo::BinaryTree;
37    /// 
38    /// let mut tree = BinaryTree::new();
39    /// let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
40    /// tree.insert(&v);
41    /// ```
42    /// 
43    pub fn new() -> Self {
44        BinaryTree(None)
45    }
46
47    /// Build a BinaryTree by a Vector
48    /// 
49    /// # Example
50    /// 
51    /// ```
52    /// use flex_algo::BinaryTree;
53    /// 
54    /// let mut tree = BinaryTree::new();
55    /// let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
56    /// tree.insert(&v);
57    /// 
58    /// ```
59    /// 
60    pub fn insert(&mut self, elements: &Vec<Option<T>>) {
61        if elements.len() == 0 {
62            return;
63        }
64        // let sides = vec!["left", "right"];
65        let mut queue = Vec::new();
66        // root node
67        self.0 = Some(Box::new(BinaryNode {
68            data: elements[0].unwrap(),
69            left: BinaryTree(None),
70            right: BinaryTree(None),
71        }));
72        let mut i = 1;
73        queue.push(self);
74
75        while queue.len() > 0 {
76            queue.rotate_left(1);
77            let current = queue.pop().unwrap();
78            if let Some(ref mut node) = current.0 {
79                // val is not None, insert left child
80                if let Some(val) = elements.get(i).unwrap() {
81                    node.left = BinaryTree(Some(Box::new(BinaryNode {
82                        data: *val,
83                        left: BinaryTree(None),
84                        right: BinaryTree(None),
85                    })));
86                }
87                i += 1;
88                if i >= elements.len() {
89                    return;
90                }
91                // check if left is None
92                if node.left.0.is_some() {
93                    queue.push(&mut node.left);
94                }
95                // if val is not None, insert right child
96                if let Some(val) = elements.get(i).unwrap() {
97                    node.right = BinaryTree(Some( Box::new(BinaryNode {
98                        data: *val,
99                        left: BinaryTree(None),
100                        right: BinaryTree(None),
101                    })));
102                }
103                i += 1;
104                if i >= elements.len() {
105                    return;
106                }
107                if node.right.0.is_some() {
108                    queue.push(&mut node.right);
109                }
110            }
111        }
112    }
113
114    /// Build a complete BinaryTree by a Vector
115    /// 
116    /// # Example
117    /// 
118    /// ```
119    /// use flex_algo::BinaryTree;
120    /// 
121    /// let mut tree = BinaryTree::new();
122    /// let v = vec![1, 2, 3, 4, 5, 6, 7];
123    /// tree.insert_as_complete(&v);
124    /// 
125    /// ```
126    /// 
127    pub fn insert_as_complete(&mut self, elements: &Vec<T>) {
128        if elements.len() == 0 {
129            return;
130        }
131        self.0 = Some(Box::new(BinaryNode {
132            data: *elements.get(0).unwrap(),
133            left: BinaryTree(None),
134            right: BinaryTree(None),
135        }));
136        let mut queue = Vec::new();
137        queue.push(self);
138        let mut count = 1;
139
140        while queue.len() > 0 {
141            queue.rotate_left(1);
142            let current = queue.pop().unwrap();
143
144            if let Some(ref mut node) = current.0 {
145                // insert left child
146                if let Some(&val) = elements.get(count) {
147                    node.left = BinaryTree(Some(Box::new(BinaryNode::new(val))));
148                }
149                count += 1;
150                if count >= elements.len() {
151                    return;
152                }
153                if node.left.0.is_some() {
154                    queue.push(&mut node.left);
155                }
156                // insert right child
157                if let Some(&val) = elements.get(count) {
158                    node.right = BinaryTree(Some(Box::new(BinaryNode::new(val))));
159                }
160                count += 1;
161                if count >= elements.len() {
162                    return;
163                }
164                if node.right.0.is_some() {
165                    queue.push(&mut node.right);
166                }
167            }
168        }
169    }
170
171    /// Traverse a BinaryTree in preorder
172    /// 
173    /// # Example
174    /// 
175    /// ```
176    /// use flex_algo::BinaryTree;
177    /// 
178    /// let mut tree = BinaryTree::new();
179    /// let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
180    /// tree.insert(&v);
181    /// tree.print_preorder(0);
182    /// 
183    /// ```
184    /// 
185    pub fn print_preorder(&self, depth: usize) {
186        if let Some(node) = &self.0 {
187            // print the left
188            node.left.print_preorder(depth + 1);
189            // print the data
190            let mut space = String::new();
191            for _ in 0..depth {
192                space.push('.');
193            }
194            println!("{}{:?}", space, node.data);
195            // print the right
196            node.right.print_preorder(depth + 1);
197        }
198    }
199
200    /// Get the depth of the BinaryTree
201    /// 
202    /// # Example
203    /// 
204    /// ```
205    /// use flex_algo::BinaryTree;
206    /// 
207    /// let mut tree = BinaryTree::new();
208    /// let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
209    /// tree.insert(&v);
210    /// 
211    /// let depth = tree.depth();
212    /// println!("depth: {}", depth);
213    /// assert_eq!(depth, 4);
214    /// ```
215    /// 
216    pub fn depth(&self) -> i32 {
217        if let Some(ref node) = self.0 {
218            if node.left.0.is_none() && node.right.0.is_none() {
219                return 1;
220            }
221            let left_depth = 1 + node.left.depth();
222            let right_depth = 1 + node.right.depth();
223            if left_depth > right_depth {
224                return left_depth;
225            }
226            return right_depth;
227        }
228        0
229    }
230
231    /// Get the level order of the BinaryTree
232    /// 
233    /// # Example
234    /// 
235    /// ```
236    /// use flex_algo::BinaryTree;
237    /// 
238    /// let mut tree = BinaryTree::new();
239    /// let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
240    /// tree.insert(&v);
241    /// 
242    /// let level_order = tree.level_order();
243    /// println!("level order: {:?}", level_order);
244    /// assert_eq!(level_order, vec![vec![1], vec![2, 3], vec![4, 5], vec![6]].to_vec());
245    /// ```
246    /// 
247    pub fn level_order(&self) -> Vec<Vec<T>> {
248        if self.0.is_none() {
249            return Vec::new();
250        }
251        let mut queue = Vec::new();
252        let mut levels = Vec::new();
253        queue.push(self);
254
255        while queue.len() > 0 {
256            let mut count = 0;
257            let current_level_size = queue.len();
258            let mut current_level_values = Vec::new();
259
260            // traverse all the nodes of current level, after look, the queue will hold the nodes of next level
261            while count < current_level_size {
262                queue.rotate_left(1);
263                let current = queue.pop().unwrap();
264                if let Some(ref node) = current.0 {
265                    current_level_values.push(node.data);
266                    count += 1;
267
268                    if node.left.0.is_some() {
269                        queue.push(&node.left);
270                    }
271                    if node.right.0.is_some() {
272                        queue.push(&node.right);
273                    }
274                }
275            }
276            levels.push(current_level_values);
277        }
278        levels
279    }
280
281    /// Get the right side view of the BinaryTree
282    /// 
283    /// # Example
284    /// 
285    /// ```
286    /// use flex_algo::BinaryTree;
287    /// 
288    /// let mut tree = BinaryTree::new();
289    /// let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
290    /// tree.insert(&v);
291    /// 
292    /// let mut res: Vec<i32> = Vec::new();
293    /// tree.right_side_view(0, &mut res);
294    /// println!("right side view: {:?}", res);
295    /// assert_eq!(res, vec![1, 3, 5, 6]);
296    /// ```
297    /// 
298    pub fn right_side_view(&self, depth: usize, res: &mut Vec<T>) {
299        if let Some(ref node) = self.0 {
300            let last_level = res.len();
301            if depth >= last_level {  
302                res.push(node.data);
303            }
304            if node.right.0.is_some() {
305                node.right.right_side_view(depth + 1, res);
306            }
307            if node.left.0.is_some() {
308                node.left.right_side_view(depth + 1, res);
309            }
310        } else {
311            return;
312        }
313    }
314
315    /// Get the left side view of the BinaryTree
316    /// 
317    /// # Example
318    /// 
319    /// ```
320    /// use flex_algo::BinaryTree;
321    /// 
322    /// let mut tree = BinaryTree::new();
323    /// let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
324    /// tree.insert(&v);
325    /// 
326    /// let mut res: Vec<i32> = Vec::new();
327    /// tree.left_side_view(0, &mut res);
328    /// println!("left side view: {:?}", res);
329    /// assert_eq!(res, vec![1, 2, 4, 6]);
330    /// ```
331    ///
332    pub fn left_side_view(&self, depth: usize, res: &mut Vec<T>) {
333        if let Some(ref node) = self.0 {
334            let current_level = res.len();
335            if depth >= current_level {
336                res.push(node.data);
337            }
338            if node.left.0.is_some() {
339                node.left.left_side_view(depth + 1, res);
340            }
341            if node.right.0.is_some() {
342                node.right.left_side_view(depth + 1, res);
343            }
344        } else {
345            return;
346        }
347    }
348
349    fn node_exists(&self, idx_to_find: i32, height: i32) -> bool {
350        let mut left = 0;
351        let mut level = 0;
352        let mut right = (2 as i32).pow(height as u32) as i32 - 1;
353        let mut node = self;
354
355        while level < height {
356            let mid = (((left + right) as f32)/(2 as f32)).ceil() as i32;
357            if idx_to_find >= mid {
358                left = mid;
359                if let Some(ref binary_node ) = node.0 {
360                    node = &binary_node.right;
361                }
362            } else {
363                right = mid - 1;
364                if let Some(ref binary_node) = node.0 {
365                    node = &binary_node.left;
366                }
367            }
368            level += 1;
369        }
370        if node.0.is_none() {
371            return false;
372        }
373        true
374    }
375
376    /// Get the height of the BinaryTree
377    /// 
378    /// # Example
379    /// 
380    /// ```
381    /// use flex_algo::BinaryTree;
382    /// 
383    /// let mut tree = BinaryTree::new();
384    /// let v = vec![1, 2, 3, 4, 5, 6, 7];
385    /// tree.insert_as_complete(&v);
386    /// 
387    /// let height = tree.height();
388    /// println!("height: {}", 2);
389    /// assert_eq!(height, 2);
390    /// ```
391    /// 
392    pub fn height(&self) -> i32{
393        self.depth() - 1
394    }
395
396    /// Get the nodes count of the complete BinaryTree
397    /// 
398    /// # Example
399    /// 
400    /// ```
401    /// use flex_algo::BinaryTree;
402    /// 
403    /// let mut tree = BinaryTree::new();
404    /// let v = vec![1, 2, 3, 4, 5, 6, 7];
405    /// tree.insert_as_complete(&v);
406    /// 
407    /// let count = tree.count_nodes();
408    /// println!("count: {}", count);
409    /// assert_eq!(count, 7);
410    /// ```
411    /// 
412    pub fn count_nodes(&self) -> i32 {
413        if self.0.is_none() {
414            return 0;
415        }
416        let height = self.height();
417        if height == 0 {
418            return 1;
419        }
420        let mut left = 0;
421        let upper_count = (2 as i32).pow(height as u32) - 1;
422        let mut right = upper_count;
423
424        while left < right {
425            let idx_to_find = (((left + right) as f32)/(2 as f32)).ceil() as i32;
426
427            if self.node_exists(idx_to_find, height) {
428                left = idx_to_find;
429            } else {
430                right = idx_to_find - 1;
431            }
432        }
433        upper_count + left + 1
434    }
435}
436
437impl<T: Copy + Debug + 'static> Display for BinaryTree<T> {
438
439    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
440        write!(f, "{:?}", self.0)
441    }
442}
443
444#[cfg(test)]
445mod tests {
446    use std::vec;
447
448    use super::*;
449
450    #[test]
451    fn test_binary_node() {
452        let node = BinaryNode::new(1);
453        println!("node: {:?}", node);
454        // panic!();
455    }
456
457    #[test]
458    fn test_binary_tree() {
459        let mut tree = BinaryTree::new();
460
461        let v = vec![Some(1), Some(2), Some(3), Some(4), Some(5), Some(6)];
462        tree.insert(&v);
463        println!("tree: {}", tree);
464        tree.print_preorder(0);
465        // panic!();
466    }
467
468    #[test]
469    fn test_binary_tree_none() {
470        let mut tree = BinaryTree::new();
471        let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
472        tree.insert(&v);
473        println!("tree: {:?}", tree);
474        tree.print_preorder(0);
475        // panic!();
476    }
477
478    #[test]
479    fn test_binary_tree_depth() {
480        let mut tree = BinaryTree::new();
481        let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
482        tree.insert(&v);
483        tree.print_preorder(0);
484        let depth = tree.depth();
485        println!("depth: {}", depth);
486        assert_eq!(depth, 4);
487        // panic!();
488    }
489
490    #[test]
491    fn test_binary_tree_level_order() {
492        let mut tree = BinaryTree::new();
493        let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
494        tree.insert(&v);
495        let level_order = tree.level_order();
496        println!("level order: {:?}", level_order);
497        assert_eq!(level_order, vec![vec![1], vec![2, 3], vec![4, 5], vec![6]].to_vec());
498        // panic!();
499    }
500
501    #[test]
502    fn test_binary_tree_right_side_view() {
503        let mut tree = BinaryTree::new();
504        let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
505        tree.insert(&v);
506        let mut res: Vec<i32> = Vec::new();
507        tree.right_side_view(0, &mut res);
508        println!("right side view: {:?}", res);
509        assert_eq!(res, vec![1, 3, 5, 6]);
510        // panic!();
511    }
512
513    #[test]
514    fn test_binary_tree_left_side_view() {
515        let mut tree = BinaryTree::new();
516        let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
517        tree.insert(&v);
518        let mut res: Vec<i32> = Vec::new();
519        tree.left_side_view(0, &mut res);
520        println!("left side view: {:?}", res);
521        assert_eq!(res, vec![1, 2, 4, 6]);
522        // panic!();
523    }
524
525    #[test]
526    fn test_binary_tree_insert_as_complete() {
527        let mut tree = BinaryTree::new();
528        let v = vec![1, 2, 3, 4, 5, 6, 7];
529        tree.insert_as_complete(&v);
530        tree.print_preorder(0);
531        // panic!();
532    }
533
534    #[test]
535    fn test_binary_tree_count_nodes() {
536        let mut tree = BinaryTree::new();
537        let v = vec![1, 2, 3, 4, 5, 6, 7];
538        tree.insert_as_complete(&v);
539        tree.print_preorder(0);
540        let count = tree.count_nodes();
541        println!("count: {}", count);
542        assert_eq!(count, 7);
543        // panic!();
544    }
545}
flex_algo/binary_tree.rs

flex_algo/
binary_tree.rs
