[Rust] Iterative & recursive | 0ms
Approach\nThe recursive version descends the tree through recursive calls with their state pushed on the execution stack. The traversal prefers the left branch 
# Approach\nThe recursive version descends the tree through recursive calls with their state pushed on the execution stack. The traversal prefers the left branch over the right, and the output is built before descending either branch.\n\nThe iterative version is very similar. It also uses a stack to preserve the state of traversal. The right branch is pushed before the left, since the left branch needs to be popped before the right. The output is updated before pushing any branches.\n\nThe cloning operations in the code don\'t clone the actual tree nodes, what\'s being cloned are the smart pointers that reference them. I don\'t believe there\'s any value in avoiding cloning these.\n\n# Complexity\n- Time complexity: $$O(n)$$ Each node is visited in turn - no searching.\n- Space complexity: $$O(n + log_2(n))$$ *auxiliary* memory used. The returned vector accounts for the $$n + $$ term. For the $$log_2(n)$$ term, the memory used when pushing an execution stack frame counts in the same way the memory used when pushing an iterative stack item counts. The height of the tree determines the max number of stack items that will be piled up at any time during traversal. Assuming the tree is balanced, the height will be $$log_2(n)$$.\n\n# Code\n```rust\nuse std::rc::Rc;\nuse std::cell::RefCell;\n\ntype NodeOpt = Option<Rc<RefCell<TreeNode>>>;\n\nimpl Solution {\n    pub fn preorder_traversal(root: NodeOpt) -> Vec<i32> {\n        Self::preorder_traversal_iter(root)\n        //let mut result = vec![];\n        //Self::preorder_traversal_recurs(root, &mut result);\n        //result\n    }\n    fn preorder_traversal_recurs(root: NodeOpt, result: &mut Vec<i32>) {\n        if let Some(pnode) = root {\n            let node = pnode.borrow();\n            result.push(node.val);\n            Self::preorder_traversal_recurs(node.left.clone(), result);\n            Self::preorder_traversal_recurs(node.right.clone(), result);\n        }\n    }\n    fn preorder_traversal_iter(root: NodeOpt) -> Vec<i32> {\n        let mut result = vec![];\n        let mut stack  = vec![root];\n        while let Some(node_opt) = stack.pop() {\n            if let Some(pnode) = node_opt {\n                let node = pnode.borrow();\n                result.push(node.val);\n                stack.push(node.right.clone());\n                stack.push(node.left.clone());\n            }\n        }\n        result\n    }\n}\n```
['Binary Tree', 'Rust']