Decode the Coding Interview in Rust: Real-World Examples/

...

/

Invert Binary Tree

Invert Binary Tree

Understand and solve the interview question "Invert Binary Tree".

We'll cover the following...

Description

In this lesson, your task is to invert a given binary tree, T.

Let’s look at an example below:

Press + to interact
main.rs
TreeNodes.rs
fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    root
}

Solution

We can solve this problem using depth-first search (DFS).

The inverse of an empty tree is the empty tree. To invert tree T with root and subtrees left and right, we keep root the same and invert the right and left subtrees.

Let’s review the implementation below:

Press + to interact
main.rs
TreeNodes.rs
fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    match &root {
      Some(node) => {
        let left = invert_tree(node.borrow().left.clone());
        let right = invert_tree(node.borrow().right.clone());
        node.borrow_mut().left = right;
        node.borrow_mut().right = left;
      }, 
      None => {}
    };
    root
}
fn main() {
    let mut root = TreeNode::new(1);
    root.left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
    root.right = Some(Rc::new(RefCell::new(TreeNode::new(3))));
    root.left.clone().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    root.left.clone().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(5))));
    root.right.clone().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(6))));
    root.right.clone().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(7))));
    let res = invert_tree(Some(Rc::new(RefCell::new(root))));
    let res1 = level_order(res);
    println!("{:?}",res1);
}

Complexity measures

Time complexity Space complexity
...