CODEWITHSUNDEEP
javasortingbinary-tree
ramuh1231
ramuh1231

Reputation: 47

Filling Binary Tree Row by Row from Array

How would one go about adding nodes to a binary tree row by row from an array? It's easy enough when elements are added in their proper position based on a key value of some sort, and I have attempted to assign keys to the values in the array in order to do the row by row adding, but I feel like there must be a more elegant way to do this.

To clarify, what I want is to take an array and convert it into a tree like this

_ _ _ 0 _ _ _

_ 1 _ _ _ 2 _

3 _ 4 _ 5 _ 6

where the numbers represent the indices the values had in the initial array

Upvotes: 1

Views: 831

Answers (1)

schmop
schmop

Reputation: 1440

Notice that the left child of a node with index i has the index 2*i+1 and the right child 2*i+2. Using that, it's very simple:

class Node<T>
{
   T val;
   Node left = null, right = null;

   public void fill(int index, T [] vals)
   {
      val = vals[index];
      if (vals.length > 2*index+1)
      {
         left = new Node<T>();
         left.fill(2*index+1, vals);
      }
      if (vals.length > 2*index+2)
      {
         right = new Node<T>();
         right.fill(2*index+2, vals);
      }
   }
}

Start with:

Node<MyValueType> root = new Node<MyValueType>();
root.fill(0, vals);

Replacing MyValueType with whatever is in your array of course.

Upvotes: 2

Related Questions