pub struct TreeNode<T> {
    pub value: T,
    pub left: Option<Box<Self>>,
    pub right: Option<Box<Self>>,
}

fn make_tree() -> TreeNode<u32> {
    //           5
    //     3            8
    //   2   4       6     9
    //  1              7
    return TreeNode {
        value: 5,
        left: Some(Box::new(TreeNode {
            value: 3,
            left: Some(Box::new(TreeNode {
                value: 2,
                left: Some(Box::new(TreeNode {
                    value: 1,
                    left: None,
                    right: None,
                })),
                right: None,
            })),
            right: Some(Box::new(TreeNode {
                value: 4,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(TreeNode {
            value: 8,
            left: Some(Box::new(TreeNode {
                value: 6,
                left: None,
                right: Some(Box::new(TreeNode {
                    value: 7,
                    left: None,
                    right: None,
                })),
            })),
            right: Some(Box::new(TreeNode {
                value: 9,
                left: None,
                right: None,
            })),
        })),
    };
}

fn traverse(node: &TreeNode<u32>) {
    if let Some(ref left) = node.left {
        traverse(left)
    }
    println!("{}", node.value);
    if let Some(ref right) = node.right {
        traverse(right)
    }
}

fn main() {
    let tree = make_tree();
    traverse(&tree);

}