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

Invert Binary Tree

Explore how to invert a binary tree by swapping left and right subtrees using depth-first search. Learn to implement this in Elixir and analyze its time and space complexity for better coding interview preparation.

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

Elixir
defmodule Solution do
  def invert_tree(_root) do
    # write your code here
  end
end

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:

Elixir
defmodule Trees do
  def invert_tree(root) when root == nil, do: root
  def invert_tree(root) do
    right = invert_tree(root.right)
    left = invert_tree(root.left)
    %TreeNode{root | left: right, right: left}
  end
end
# Driver Code
defmodule Main do
  def main do
    IO.puts "-----------------------------"
    IO.puts "PROGRAM OUTPUT:"
    root = TreeNode.init(1)
    root = %TreeNode{root | left: TreeNode.init(2)}
    root = %TreeNode{root | right: TreeNode.init(3)}
    root = %TreeNode{root | left: %TreeNode{root.left | left: TreeNode.init(4)}}
    root = %TreeNode{root | left: %TreeNode{root.left | right: TreeNode.init(5)}}
    root = %TreeNode{root | right: %TreeNode{root.right | left: TreeNode.init(6)}}
    root = %TreeNode{root | right: %TreeNode{root.right | right: TreeNode.init(7)}}
    Printing.print_tree(Trees.invert_tree(root))
  end
end

Complexity measures

Time Complexity Space Complexity
...