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

...

/

Binary Tree Right Side View

Binary Tree Right Side View

Understand and solve the interview question "Binary Tree Right Side View".

We'll cover the following...

Description

You are given a binary tree T. Imagine you are standing to the right of it; you have to return the value of the nodes you can see from top to bottom.

You have to return the rightmost nodes on their respective levels in the form of an array.

Let’s discuss an example below:

Coding exercise

Press + to interact
main.exs
TreeNode.ex
defmodule Solution do
  def right_side_view(_root) do
    # write your code here
  end
end

Solution

We can use a depth-first search (DFS) to solve this problem. The intuition here is to traverse the tree level by level recursively, starting from the rightmost node for each recursive call.

Let’s review the implementation below:

Press + to interact
main.exs
TreeNode.ex
defmodule BinaryTree do
    def dfs(node, level, rightside) do
        rightside =
            cond do
                level == length(rightside) -> [node.val | rightside]
                true -> rightside
            end        
        [node.right, node.left]
        |> Enum.reduce(rightside, fn(child, rightside) ->
            cond do
                child != nil -> dfs(child, level + 1, rightside)
                true -> rightside
            end
        end)
    end
    def right_side_view(root) when root == nil, do: []
    def right_side_view(root) do
        rightside = []
        dfs(root, 0, rightside) |> :lists.reverse
    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)}}
    inner_left = %TreeNode{root.right.right | left: TreeNode.init(8)}
    root = %TreeNode{root | right: %TreeNode{root.right | right: inner_left}}
    IO.inspect BinaryTree.right_side_view(root)
  end
end

Complexity measures

Time Complexity
...