Decode the Coding Interview in Elixir: 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 a binary tree, T.

Let’s look at an example below:

Coding exercise

Press + to interact
main.exs
TreeNode.ex
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:

Press + to interact
main.exs
TreeNode.ex
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
...