How do implement height of a binary search tree recursively using elixir?

Question

I am using Elixir to write some programs for binary search trees and have run into a roadblock with a function to calculate height recursively.

The basic recursive formula for the height of a tree goes as follows.

If tree is empty then return 0
Else
1. Get the max depth of left subtree recursively i.e., call maxDepth( tree->left-subtree)
2. Get the max depth of right subtree recursively i.e., call maxDepth( tree->right-subtree)
3. Get the max of max depths of left and right subtrees and add 1 to it for the current node. max_depth = max(max dept of left subtree,max depth of right subtree) + 1
4. Return max_depth

For my part, I am getting the following error when I try to test out the function with a generic node structure.

** (ArithmeticError) bad argument in arithmetic expression

I tried removing the addition of 1 to left_depth and right_depth. That removed the arithmetic error but I'm also not getting any numerical result (height) to show up.

Here is my height function. As you can see, it follows the recursive format pretty much to the letter.

# calculate the height
@spec height(bst_node) :: number
def height(node) do
  if is_nil(node) do
    IO.puts "No tree exists. The height is 0"
  else
    left_depth =  height(node.left)
    right_depth = height(node.right)
    if left_depth >= right_depth do
        left_depth + 1
        IO.puts "The height of the tree is #{left_depth + 1}"
    else
      right_depth + 1
      IO.puts "The height of the tree is #{right_depth + 1}"
    end
  end
end

I would prefer to be able to execute this height function recursively in elixir but it is certainly not the end of the world if I have to resort to non-recursive means to get it done. This should just display the height of a generic tree.

You never specify the number that height is supposed to return, even though you calculate it. — Scott Hunter
Try it with all IO calls on a line of code that precedes any return value and make sure you have a numerical return value when the node is nil. — גלעד ברקן

Adam Millerchip Adam Millerchip · Accepted Answer · 2019-04-20T04:19:03

There are three features of elixir that are very useful when implementing recursive solutions:

Parameter pattern matching
Multiple function clauses
Tail-call optimization

Here's an example solution that uses the first two features:

defmodule Tree do
  defstruct [:left, :right]

  def height(%Tree{left: nil,  right: nil}),   do: 0
  def height(%Tree{left: nil,  right: right}), do: 1 + height(right)
  def height(%Tree{left: left, right: nil}),   do: 1 + height(left)
  def height(%Tree{left: left, right: right}), do: 1 + max(height(left), height(right))
end

First, define a struct called Tree with left and right to represent our tree.

Then we define 4 clauses of a height function that uses pattern matching to inspect the Tree's left and right values.

If both left and right are nil, then we are a leaf and can return height 0
If one of the children is nil, then we can return the height of the non-nil tree, plus 1 for ourself (the current node).
Same as above.
The final clause deals with the case where both children are non-nil. In that case, return the maximum of the height of the two children, plus 1 for ourself.

Note that the 1 + recursive_call() style will result in a stack of recursive calls, because it has to keep track of the height of the child nodes in the call stack in order to finally perform the 1 + operation. We can minimize this by passing the in-progress height as an acc accumulator parameter to the function, and taking advantage of tail-call optimization, which allows the compiler to reduce the number of stack frames needed when a the last thing a function does is to call itself. In this case, we still have to calculate the max of the two subtrees in the final clause, which means we're not using a tail-call in the majority of the cases, but I included it for completeness.:

def height_tailcall(%Tree{left: nil, right: nil}, acc), do: acc

def height_tailcall(%Tree{left: nil, right: right}, acc) do
  height_tailcall(right, acc + 1)
end

def height_tailcall(%Tree{left: left, right: nil}, acc) do
  height_tailcall(left, acc + 1)
end

def height_tailcall(%Tree{left: left, right: right}, acc) do
  max(height_tailcall(left, acc + 1), height_tailcall(right, acc + 1))
end

Example:

def example do
  leaf = %Tree{}
  height1 = %Tree{left: leaf,    right: leaf}
  height2 = %Tree{left: height1, right: height1}
  height3 = %Tree{left: height2, right: height1}
  height4 = %Tree{left: nil,     right: height3}

  IO.inspect(height(leaf),    label: "leaf")
  IO.inspect(height(height1), label: "height1")
  IO.inspect(height(height2), label: "height2")
  IO.inspect(height(height3), label: "height3")
  IO.inspect(height(height4), label: "height4")

  IO.inspect(height_tailcall(leaf, 0), label: "leaf (tail recursion)")
  IO.inspect(height_tailcall(height1, 0), label: "height1 (tail recursion)")
  IO.inspect(height_tailcall(height2, 0), label: "height2 (tail recursion)")
  IO.inspect(height_tailcall(height3, 0), label: "height3 (tail recursion)")
  IO.inspect(height_tailcall(height4, 0), label: "height4 (tail recursion)")

  height4
end

Output:

leaf: 0
height1: 1
height2: 2
height3: 3
height4: 4
leaf (tail recursion): 0
height1 (tail recursion): 1
height2 (tail recursion): 2
height3 (tail recursion): 3
height4 (tail recursion): 4
%Tree{
  left: nil,
  right: %Tree{
    left: %Tree{
      left: %Tree{
        left: %Tree{left: nil, right: nil},
        right: %Tree{left: nil, right: nil}
      },
      right: %Tree{
        left: %Tree{left: nil, right: nil},
        right: %Tree{left: nil, right: nil}
      }
    },
    right: %Tree{
      left: %Tree{left: nil, right: nil},
      right: %Tree{left: nil, right: nil}
    }
  }
}

How do implement height of a binary search tree recursively using elixir?

2 Answers