How to pre-order a binary tree in a function without moving its root node?

Question

I'm pretty new to Rust and after reading some chapters of Official Rust Book I started to coding some data structure stuff. I chose to create a simple binary tree and perform a simple pre-order twice. So I write a simple program:

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}
impl TreeNode {
    fn new(val: i32, left: Option<Box<TreeNode>>, right: Option<Box<TreeNode>>) -> TreeNode {
        TreeNode { val, left, right }
    }
}
fn main() {
    let root = TreeNode::new(
        120,
        Some(Box::new(TreeNode::new(
            150,
            Some(Box::new(TreeNode::new(180, None, None))),
            Some(Box::new(TreeNode::new(40, None, None))),
        ))),
        Some(Box::new(TreeNode::new(
            110,
            Some(Box::new(TreeNode::new(144, None, None))),
            None,
        ))),
    );
    pre_order(Some(Box::new(root)));
    pre_order(Some(Box::new(root)));
}
fn pre_order(root: Option<Box<TreeNode>>) {
    match root {
        None => {
            return;
        }
        Some(root_node) => {
            println!("{} ", root_node.val);
            pre_order(root_node.left);
            pre_order(root_node.right);
        }
    }
}

This program won't compile because the first pre-order function has already moved the root node so the second function gets nothing. That's not right. A pre-order function shouldn't eating its root node. I knew that passing an argument by its reference will prevent the function from this situation, so I add a reference... before what? Option? Box? TreeNode? I decide to add them all. So I modified the function like this:

fn pre_order(root: &Option<&Box<&TreeNode>>) {
    match root {
        None => {
            return;
        }
        Some(root_node) => {
            println!("{} ", root_node.val);
            pre_order(&&&root_node.left);
            pre_order(&&&root_node.right);
        }
    }
}

And changed the way I call it:

pre_order(&Some(&Box::new(&root)));
pre_order(&Some(&Box::new(&root)));

However, the checking tool warns me:

error[E0308]: mismatched types
  --> src/main.rs:35:23
   |
35 |             pre_order(&&&root_node.left);
   |             --------- ^^^^^^^^^^^^^^^^^ expected enum `Option`, found reference
   |             |
   |             arguments to this function are incorrect
   |
   = note: expected reference `&Option<&Box<&TreeNode>>`
              found reference `&&&Option<Box<TreeNode>>`
note: function defined here
  --> src/main.rs:28:4
   |
28 | fn pre_order(root: &Option<&Box<&TreeNode>>) {
   |    ^^^^^^^^^ ------------------------------

error[E0308]: mismatched types
  --> src/main.rs:36:23
   |
36 |             pre_order(&&&root_node.right);
   |             --------- ^^^^^^^^^^^^^^^^^^ expected enum `Option`, found reference
   |             |
   |             arguments to this function are incorrect
   |
   = note: expected reference `&Option<&Box<&TreeNode>>`
              found reference `&&&Option<Box<TreeNode>>`
note: function defined here
  --> src/main.rs:28:4
   |
28 | fn pre_order(root: &Option<&Box<&TreeNode>>) {
   |    ^^^^^^^^^ ------------------------------

For more information about this error, try `rustc --explain E0308`.

I was confused. How possibly can I change type &&&Option<Box<TreeNode>> to &Option<&Box<&TreeNode>>? I don't think I'm doing it right. Which part should I add the reference? Option, Box or TreeNode? How to design that pre_order function, so that I can pass the reference of the tree nodes recursively without actually consuming it? Do I need Rc, Refcell, Lifetime specifier or any advanced feature to do this?

Answer 1

To fix this problem, you need to understand that boxing a value also moves it into a box, i.e. you can neither box nor wrap into an option the same value (root in this case) twice. The quick solution is to wrap the root immediately on creation:

let root = Some(Box::new(TreeNode::new(/*...*/)));
pre_order(&root);
pre_order(&root);

and pass the reference to the function:

fn pre_order(root: &Option<Box<TreeNode>>) {
    match root {
        None => {
            return;
        }
        Some(root_node) => {
            println!("{} ", root_node.val);
            pre_order(&root_node.left);
            pre_order(&root_node.right);
        }
    }
}

Playground