Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Ruby: Real-World Examples

Invert Binary Tree

Explore how to invert a binary tree by recursively swapping left and right subtrees using depth-first search. Understand the time and space complexity involved and apply this knowledge to solve similar tree manipulation problems in coding interviews.

We'll cover the following...

Description

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

Let’s look at an example below:

Coding exercise

Ruby
require './TreeNode.rb'
def invert_tree(root)
end
Invert binary tree

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:

Ruby
require './TreeNode.rb'
def invert_tree(root) 
    if root == nil  
      return root
    end
    
    right = invert_tree(root.right);
    left = invert_tree(root.left);
    root.left = right;
    root.right = left;
    return root;
end
# Driver Code
root = TreeNode.new(1)
root.left = TreeNode.new(2)
root.right = TreeNode.new(3)
root.left.left = TreeNode.new(4)
root.left.right = TreeNode.new(5)
root.right.left = TreeNode.new(6)
root.right.right = TreeNode.new(7)
print_tree(invert_tree(root))
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...