Thread: adding items to a binary tree

I am trying to make a class to build a simple tree. If we have a root as item #1, the next item added (#2) would be its left child. The next item added (#3) would be placed as the right child. The method would sense there are out of options and to go to the far left and use the next depth: Item #4 would be the left child of item #2 and item #5 would be the right child of #2 as well. This would just keep continuing as items are added. What type of steps would it take to do this?

There's actually a very simple way to do this.

Consider a simple array. We'll assume a variable sized array, which you can do in Java without too much trouble.

Say you want to make a tree with the items 3, 2, 7, 1, and 4, in that order, so the root is 3, 3's left child is 2, and 2's right child is 4. Consider the representation of this tree as just the array [3, 2, 7, 1, 4]. All we really need to be able to call this representation a tree is an easy way of telling which indices in the array correspond to left and right children, and which nodes are related in this way.

Well, just from this example, we know 2 and 1 are left children of 3 and 2, respectively.We notice that the indices of 2 and 1 are 2 and 4, respectively. The indices of 3 and 2 are 1 and 2, respectively. From this example, it seems possible that the relation "is a left child of" can be found from the representation by checking "has index equal to twice the index of". So...

X is a left child of Y iff X has index equal to twice the index of Y.

It just so happens that the following happens in our example:

X is a right child of Y iff X has index equal to twice the index of Y plus 1.

These happen to be true in general. Notice that I am indexing from 1 in my example... if you index from 0, you'll need to work out your own relations involving the indices (hint: the multiplying by 2 is still the right idea... but what do you need to add in each case?)

So under this scheme the array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is uniquely decodable as

     1
    2 3
   4 5 6
  7 8 9 10

Here's some pseudocode. The implementation details I'll leave to you, as they're pretty easy.

 
!!! assuming the existence of an array with arbitrary capacity, adds a new object to the end of it !!!
AddToTree(value : Object)
1. storage[Size() + 1] := value
 
!!! returns the number of items in storage !!!
Size()
1. return the number of items in storage
 
Value(index : integer)
1. if index > Size() then return null
2. else then return storage[index]
 
!!! given the index of a node in the tree, returns the index of the node's left child !!!
LeftChild(node : integer)
1. if node * 2 > Size() then return null
2. else then return node * 2
 
!!! given the index of a node in the tree, returns the index of the node's right child !!!
RightChild(node : integer)
1. if node * 2 + 1 > Size() then return null
2. else then return node * 2 + 1

Then you could have code that looked like this...

 
AddToTree("cat")
AddToTree("dog")
AddToTree("tree")
AddToTree("cup")
AddToTree("meat")
AddToTree("house")
AddToTree("hat")
 
print(Value(1)) !!! prints "house" !!!
print(Value(LeftChild(1))) !!! prints "dog" !!!
print(Value(RightChild(LeftChild(1)))) !!! prints "meat" !!!

Let me know if that needs any further clarification.