Build binary tree from level order array

[Eiji]

@al2o3cr

I believe the error in your diagram is the two -1s under the -1 that’s a right-child of 4. -1s on a given level shouldn’t consume any input values in the next level.

Weird … it’s like save the space no matter what (here I mean confusion of people new in topic). It’s my first time using it and such assumption looks really bad at this part. Anyway, in that case my first code would not work as there’s no algorithm which can dynamically count the proper index without so much context.

However my second example is really easy to modify. Here goes an updated version which handles both use cases depends on custom_count option:

defmodule TreeNode do
  defstruct ~w[data left right]a
end

defmodule Example do
  def sample(input, opts \\ [custom_count: false]) do
    input |> split(opts) |> transform(nil, opts)
  end

  # we split a list by count
  # on top is only root, so default count is always 1
  # every other level have count * 2 nodes
  defp split(list, acc \\ [], count \\ 1, opts) do
    {left, right} = Enum.split(list, count)

    # we call split until right side is empty
    if right == [] do
      [left | acc]
    else
      # after each split the left side is added to acc
      # therefore we would have leafs list as fist item in acc
      # and a single root data as last item of acc
      count = if opts[:custom_count], do: Enum.count(left, &(&1 != -1)), else: count
      split(right, [left | acc], count * 2, opts)
    end
  end

  defp transform([leafs | groups], nil, opts) do
    # transform leafs into initial acc
    # which would be used in transform groups 
    transform(groups, {Enum.map(leafs, &transform_leaf/1), []}, opts)
  end

  # finishing by returning root node
  defp transform([], {[root_node], []}, _opts), do: root_node

  defp transform([[] | groups], {[], acc_right}, opts) do
    # reached end of group
    # all nodes we have collected in acc_right
    # are moved to acc_left
    # so they would be used in next group
    transform(groups, {Enum.reverse(acc_right), []}, opts)
  end

  defp transform([[-1 | group] | groups], {acc_left, acc_right}, opts) do
    # skipping -1 as it should not consume leafs
    custom_count = opts[:custom_count]

    acc_left =
      case acc_left do
        acc_left when custom_count == true -> acc_left
        [] -> []
        [nil, nil | acc_left] -> acc_left
      end

    transform([group | groups], {acc_left, [nil | acc_right]}, opts)
  end

  defp transform([[data | group] | groups], {[], acc_right}, opts) do
    # node #{data} does not have children
    transform([group | groups], {[], [transform_node(data) | acc_right]}, opts)
  end

  defp transform([[data | group] | groups], {[left], acc_right}, opts) do
    # node #{data} have only left child
    transform([group | groups], {[], [transform_node(data, left) | acc_right]}, opts)
  end

  defp transform([[data | group] | groups], {[left, right | acc_left], acc_right}, opts) do
    # node #{data} have both children
    transform([group | groups], {acc_left, [transform_node(data, left, right) | acc_right]}, opts)
  end

  defp transform_leaf(-1), do: nil
  defp transform_leaf(data), do: %TreeNode{data: data}

  defp transform_node(data, left \\ nil, right \\ nil) do
    # transforming node
    %TreeNode{data: data, left: left, right: right}
  end
end

input = [5, 4, 8, 11, -1, 17, 4, 7, -1, -1, -1, 5, -1, -1, -1, -1]

iex> Example.sample(input)
%TreeNode{
  data: 5,
  left: %TreeNode{
    data: 4,
    left: %TreeNode{
      data: 11,
      left: %TreeNode{data: 7, left: nil, right: nil},
      right: nil
    },
    right: nil
  },
  right: %TreeNode{
    data: 8,
    left: %TreeNode{
      data: 17,
      left: %TreeNode{data: 5, left: nil, right: nil},
      right: nil
    },
    right: %TreeNode{data: 4, left: nil, right: nil}
  }
}

iex> Example.sample(input, custom_count: true)
%TreeNode{
  data: 5,
  left: %TreeNode{
    data: 4,
    left: %TreeNode{
      data: 11,
      left: %TreeNode{data: 7, left: nil, right: nil},
      right: nil
    },
    right: nil
  },
  right: %TreeNode{
    data: 8,
    left: %TreeNode{data: 17, left: nil, right: nil},
    right: %TreeNode{
      data: 4,
      left: %TreeNode{data: 5, left: nil, right: nil},
      right: nil
    }
  }
}

I changed only 2 things here:

1. Optionally change the count before passing to split/4 call
2. Handling transformation of -1 entries (case statement)