# Build binary tree from level order array

I am new to elixer, I need some help to construct binary tree from list of element(given in level order). Due to immutability i’m facing difficutly to implement this.
For ex: [1, 2, 3, -1, -1, -1, -1] will be represented as:

``````                  1
/   \
2       3
``````

Here -1 means, node will be null.

Expected Output Format:

``````TreeNode{
data: 1,
left: TreeNode{
data: 2,
left: nil,
right: nil
},
right: TreeNode{
data: 3,
left: nil,
right: nil
}
}

``````

In ruby, we can implement in this way.

``````def input_tree(input)
val = input[0]
input.shift()
root = TreeNode.new(val)
queue = []
queue.push(root)

while queue.size > 0
current_node = queue[0]
queue.shift()

leftValue = input[0]
input.shift()

rightValue = input[0]
input.shift()

if leftValue != -1
leftNode = TreeNode.new(leftValue)
current_node.left = leftNode
queue.push(leftNode)
end

if rightValue != -1
rightNode = TreeNode.new(rightValue)
current_node.right = rightNode
queue.push(rightNode)
end
end
return root
end
``````

TIA

have you tried using gb_trees from erlang?
https://www.erlang.org/doc/man/gb_trees.html

1 Like
1 Like

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

1 Like

(…) 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) (…)

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}
}
``````
3 Likes

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: data structures - How to build an incomplete binary tree from array representation - Stack Overflow
ex:
For the input: [5,4,8,11,-1,17,4,7,-1,-1,-1,5, -1, -1, -1, -1]
Actual tree representation:

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.

1 Like

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 `-1`s under the `-1` that’s a right-child of `4`. `-1`s on a given level shouldn’t consume any input values in the next level.

3 Likes

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)
1 Like

Thanks everyone for quick help.