Search⌘ K
Home
Courses
Decode the Coding Interview in Rust: Real-World Examples

Invert Binary Tree

Explore how to invert a binary tree by applying depth-first search in Rust. Understand the recursive approach to swapping subtrees and analyze the algorithm's time and space complexity for efficient tree manipulation.

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:

Rust 1.57.0
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:

Rust 1.57.0
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
...