Filling Binary Tree Row by Row from Array

Question

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

I know how to do inorder traversals and adding based on key values. I just don't really know how to "jump" back and forth between branches to add things row by row — ramuh1231
– ramuh1231, Commented May 18, 2014 at 3:40

schmop · Accepted Answer · 2014-05-20 17:33:41Z

2

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.

edited May 20, 2014 at 17:33

answered May 20, 2014 at 4:15

schmop

1,4401 gold badge12 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Filling Binary Tree Row by Row from Array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related