1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

use std::cell::RefCell;
use std::rc::Rc;
use std::collections::VecDeque;

pub type TreeLink = Option<Rc<RefCell<TreeNode>>>;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: TreeLink,
    pub right: TreeLink,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}


pub fn build_tree<const N: usize>(v: [i32; N]) -> TreeLink {
    if v.len() == 0 {
        None
    } else {
        let mut stack: VecDeque<TreeLink> = VecDeque::new();
        let mut root: TreeLink = None;

        for i in v {
            match stack.front_mut() {
                Some(front) => {
                    if let Some(node) = front.clone() {
                        match &mut *node.borrow_mut() {
                            n @ TreeNode { val: _, left: None, right: None } => {
                                let new_node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
                                n.left = new_node.clone();
                                stack.push_back(new_node);
                            }
                            n @ TreeNode { val: _, left: Some(_), right: None } => {
                                let new_node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
                                n.right = new_node.clone();
                                stack.push_back(new_node);
                                stack.pop_front();
                            }
                            _ => panic!("Bitchy at {i}, shouldn't happen!")
                        }
                    }
                }
                None => {
                    let node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
                    root = node.clone();
                    stack.push_back(node);
                }
            };
        }
        root
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn get_tree_link_val(node: &TreeLink) -> i32 {
        if let Some(node) = node.clone() {
            node.borrow().val
        } else {
            panic!("Node was empty!")
        }
    }

    #[test]
    fn build_tree_works() {
        let tree = &build_tree([1,2,3]);
        assert_eq!(get_tree_link_val(tree), 1);
        if let Some(node) = tree.clone() {
            let node = &node.borrow();
            assert_eq!(get_tree_link_val(&node.left), 2);
            assert_eq!(get_tree_link_val(&node.right), 3);
        } else {
            panic!("Tree was None")
        }
    }

}