Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## 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?

2. ## Re: adding items to a binary tree

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```

3. ## The Following User Says Thank You to CT&SC For This Useful Post:

vendetta (February 26th, 2010)

4. ## Re: adding items to a binary tree

the java code from 1 thru 10 is on the right track, any idea what the program or method would look like?

5. ## Re: adding items to a binary tree

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 !!!
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...

```

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.

6. ## The Following User Says Thank You to CT&SC For This Useful Post:

vendetta (February 26th, 2010)

7. ## Re: adding items to a binary tree

great ideas! thank you much