Build binary tree from level order array

have you tried using gb_trees from erlang?

https://stackoverflow.com/questions/73528430/build-binary-tree-from-level-order-array

Hi @chandan374 can you show what you’ve tried so far?

(…) if a node has an index i , its children are found at indices 2i+1 (for the left child) and 2i+2 (for the right) (…)

Source: Arrays at Binary tree | Wikipedia

With above writing code is really simple:

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

defmodule Example do
  def sample(input, index \\ 0) do
    data = Enum.at(input, index)

    unless data in [nil, -1] do
      %TreeNode{
        data: data,
        left: sample(input, index * 2 + 1),
        right: sample(input, index * 2 + 2)
      }
    end
  end
end

iex> Example.sample([1, 2, 3, -1, -1, -1, -1])
%TreeNode{
  data: 1,
  left: %TreeNode{data: 2, left: nil, right: nil},
  right: %TreeNode{data: 3, left: nil, right: nil}
}

Hi @Eiji , thanks for the help.
Sorry i didn’t provided complete context in question. Above approach will work only if given input is for complete tree.
Please check 1st answer of: https://stackoverflow.com/questions/37941318/how-to-build-an-incomplete-binary-tree-from-array-representation
ex:
For the input: [5,4,8,11,-1,17,4,7,-1,-1,-1,5, -1, -1, -1, -1]
Actual tree representation:

Screenshot 2022-08-30 at 2.32.40 AM616×332 17.5 KB

Have implemented one basic solution.
Please ingore code quality , its my 2nd day with elixir.

Approach: Provided unique id to each node, created a map that will map parent_node_id => (left_child_id, right_child_id). Once map is created, Recursively calling on root_id to build the tree.

Code:

defmodule TempTreeNode do
  defstruct [ data: nil, left_id: nil, right_id: nil, id: nil]

  def new(data, unique_id) do
    %__MODULE__{data: data, left_id: nil, left_id: nil, id: unique_id}
  end

  defp input([], _, _, map_node_and_id), do: map_node_and_id
  defp input(input_list, q, unique_id, map_node_and_id) do
    [left_elem, right_elem| input_list] = input_list
    {{:value, current_node}, q} = :queue.out(q)
    new_em = current_node

    left_node = if left_elem != -1  do TempTreeNode.new(left_elem, unique_id + 1) end
    right_node = if right_elem != -1  do TempTreeNode.new(right_elem, unique_id + 2) end

    q = if left_node != nil do :queue.in(left_node, q) else q end
    q = if right_node != nil do :queue.in(right_node, q) else q end

    new_em = if left_node != nil do %{current_node | left_id: left_node.id} else new_em  end
    new_em = if right_node != nil do %{new_em | right_id: right_node.id} else new_em  end

    map_node_and_id = Map.put(map_node_and_id, current_node.id, new_em)
    input(input_list, q, unique_id + 3, map_node_and_id)
  end

  def input_temp_tree(input_list) do
    unique_id = 1
    map_node_and_id = %{}
    [first_element| input_list] = input_list
    q = :queue.new()
    tree_node = TempTreeNode.new(first_element, unique_id)
    q = :queue.in(tree_node, q)
    input(input_list , q, unique_id, map_node_and_id)
  end
end

defmodule TreeNode do
  defstruct [ data: nil, left: nil, right: nil ]

  def new(data \\ 0) do
    %__MODULE__{data: data, left: nil, right: nil}
  end

  def construct_tree(map_node_and_id, unique_id) do
    curr_node = Map.get(map_node_and_id, unique_id)

    if curr_node != nil do
      %TreeNode{
        data: curr_node.data,
        left: construct_tree(map_node_and_id, curr_node.left_id),
        right: construct_tree(map_node_and_id, curr_node.right_id)
      }
    end
  end

  def input_tree(input_list) do
    map_node_and_id = TempTreeNode.input_temp_tree(input_list)
    construct_tree(map_node_and_id, 1)
  end
end

Is there any better approach i can use?

Above approach will work only if given input is for complete tree.

Actually, @Eiji’s approach will work also for incomplete trees, as long as the missing nodes are marked with -1, like in your example [5,4,8,11,-1,17,4,7,-1,-1,-1,5, -1, -1, -1, -1]:

iex(5)> Example.sample([5,4,8,11,-1,17,4,7,-1,-1,-1,5, -1, -1, -1, -1])
%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}
  }
}

The tree representation you provided is incorrect as 5 leaf should be a left child of 17 node. Therefore I think my example is working.

This is how it should look:

                           5
                      /         \
                     4            8
                   /   \        /    \
                  11    -1     17     4
                 /  \   / \   / \    / \
                7   -1 -1 -1  5 -1  -1 -1
               /
             -1

# after removing -1 entries

                        5
                      /   \
                     4     8
                    /     /  \
                   11    17   4
                  /     /
                 7     5

To prove that I have also wrote another solution. This time my code is building the tree in reverse mode (I’m starting with leafs) based on pattern matching.

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

defmodule Example do
  def sample(input) do
    input |> split() |> transform(nil)
  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) 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
      split(right, [left | acc], count * 2)
    end
  end

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

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

  defp transform([[] | groups], {[], acc_right}) 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), []})
  end

  defp transform([[-1 | group] | groups], {[], acc_right}) do
    # skipping -1 with no fake leafs
    transform([group | groups], {[], [nil | acc_right]})
  end

  defp transform([[-1 | group] | groups], {[nil, nil | acc_left], acc_right}) do
    # skipping -1 with transformed fake leafs
    transform([group | groups], {acc_left, [nil | acc_right]})
  end

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

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

  defp transform([[data | group] | groups], {[left, right | acc_left], acc_right}) do
    # node #{data} have both children
    transform([group | groups], {acc_left, [transform_node(data, left, right) | acc_right]})
  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

iex> Example.sample([5, 4, 8, 11, -1, 17, 4, 7, -1, -1, -1, 5, -1, -1, -1, -1])
%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}
  }
}

Both examples returns exactly same data. Feel free to ask if you have any questions.

Here’s an approach that uses a pair of recursive functions:

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

defmodule TreeBuild do
  @nothing -1

  def run([root | rest]) do
    [[left, right]] = subnodes(1, rest)
    %TreeNode{data: root, left: left, right: right}
  end

  def subnodes(0, []), do: []
  def subnodes(count, input) do
    {roots, rest} = Enum.split(input, 2*count)

    next_count = Enum.count(roots, & &1 != @nothing)

    child_nodes = subnodes(next_count, rest)

    roots
    |> build_nodes(child_nodes, [])
    |> Enum.chunk_every(2, 2, [nil])
  end

  def build_nodes([], _, acc), do: Enum.reverse(acc)
  def build_nodes([@nothing | roots], child_nodes, acc) do
    build_nodes(roots, child_nodes, [nil | acc])
  end
  def build_nodes([root | roots], [], acc) do
    node = %TreeNode{data: root, left: nil, right: nil}
    build_nodes(roots, [], [node | acc])
  end
  def build_nodes([root | roots], [[left, right] | child_nodes], acc) do
    node = %TreeNode{data: root, left: left, right: right}
    build_nodes(roots, child_nodes, [node | acc])
  end
end

TreeBuild.run([1, 2, 3, -1, -1, -1, -1])

TreeBuild.run([5,4,8,11,-1,17,4,7,-1,-1,-1,5, -1, -1, -1, -1])

Some notes on the implementation:

• the sample input has one fewer -1 on the end than I expected at first; this version of build_nodes is tolerant of any number of trailing -1s.
• chunk_every is used to tidily handle cases where build_nodes returns an odd number of nodes by providing a nil for leftovers

@Eiji 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)