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

#[derive(Debug)]
struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let order: Rc<RefCell<Vec<i32>>> = Rc::new(RefCell::new(Vec::new()));
    fn recurse(node: Option<Rc<RefCell<TreeNode>>>, a: Rc<RefCell<Vec<i32>>>) {
        if let Some(n) = node {
            a.borrow_mut().push(n.borrow().val);
            if let Some(left_n) = &n.borrow().left {
                recurse(Some(Rc::clone(left_n)), Rc::clone(&a));
            } if let Some(right_n) = &n.borrow().right {
                recurse(Some(Rc::clone(right_n)), Rc::clone(&a));
            };
        };
    }
    recurse(root, Rc::clone(&order));
    match Rc::try_unwrap(order) {
        Ok(ref_cell) => {
            ref_cell.into_inner()
        },
        Err(err) => panic!("{:?}", err),
    }
}


fn main () {
    let case = TreeNode {
        val: 2,
        left: Some(Rc::new(RefCell::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Rc::new(RefCell::new(TreeNode{
                val: 5,
                left: None,
                right: Some(Rc::new(RefCell::new(TreeNode{
                    val: 4,
                    left: None,
                    right: None,
                }))),
            }))),
        }))),
        right: Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: None,
            right: None,
        }))),
    };
    // let case = TreeNode {
    //     val: 1,
    //     left: None,
    //     right: Some(Rc::new(RefCell::new(TreeNode {
    //         val: 2,
    //         right: None,
    //         left: Some(Rc::new(RefCell::new(TreeNode{
    //             val: 3,
    //             right: None,
    //             left: None,
    //         }))),
    //     }))),
    // };
    println!("{:?}", preorder_traversal(Some(Rc::new(RefCell::new(case)))));
}