Build binary tree from level order array

chandan374

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

11 comments

#trees

0 1611 11

2022-08-30 03:46:25 UTC

Marked As Solved

al2o3cr

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.

Post #9

Also Liked

Eiji

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

Post #4