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

# Thread: Java Binary Tree (Beginners)?

1. ## Java Binary Tree (Beginners)?

I'm suppose to add up all the number that are in a node of a binary tree.

Is this correct???

This is just the algorithm:::

```static int weight(BinaryTree t, Node v)
if t.size == 0 then //if BinaryTree t is an empty tree
return 0
else

if t.hasLeft(v) then /** if Node v of BinaryTree t doesn't have a left children, it means Node v is an external node. */
return v.element
else
return weight(t, t.left(v)) + weight(t, t.right(v))```

2. ## Re: Java Binary Tree (Beginners)?

```if t.hasLeft(v) then /** if Node v of BinaryTree t doesn't have a left children, it means Node v is an external node. */
return v.element
else
return weight(t, t.left(v)) + weight(t, t.right(v))```
It looks like you're assuming that if a node doesn't have a left child, it must not have a right child. That assumption is not necessarily true for binary trees.

I would suggest implementing a true in-order traversal:

1. Check to see if there's a left child. If there is, get the weight of the left child. Set the calculated weight of this node to that value. Otherwise, set the calculated weight of this node to zero.
2. Add the value of the current node to the calculated weight of this node.
3. Check to see if there's a right child. If there is, add the weight of the right child to the calculated weight of this node.
4. return the calculated weight.

3. ## The Following User Says Thank You to helloworld922 For This Useful Post:

IAmHere (June 18th, 2011)

4. ## Re: Java Binary Tree (Beginners)?

Originally Posted by helloworld922
I would suggest implementing a true in-order traversal:

1. Check to see if there's a left child. If there is, get the weight of the left child. Set the calculated weight of this node to that value. Otherwise, set the calculated weight of this node to zero.
2. Add the value of the current node to the calculated weight of this node.
3. Check to see if there's a right child. If there is, add the weight of the right child to the calculated weight of this node.
4. return the calculated weight.

I was about to do it your way, but I notice that in my book, there's no method t.hasRight(v) and t.right(v) . It only checks for the left children.
So, I guess I have to stick to my original code.

Is my code on my first post correct?

5. ## Re: Java Binary Tree (Beginners)?

Only if the assumption I said holds. Actually, the assumption you're making is:

If and only if node v has a left child, then there must be a right child.

I can think of several scenarios where this is not true.

Consider the tree with 2 elements:

1 2

There is no possible way the above assumption could be true, since one of these elements must be the root node, and the other must be either the left child or the right child, but not both.

I would suggest thoroughly reading your book to make sure that this kind of scenario will not happen. If this scenario can happen, then your book is wrong (don't worry, it happens). In the real world, I can tell you that this assumption is almost always a bad assumption.

6. ## The Following User Says Thank You to helloworld922 For This Useful Post:

IAmHere (June 18th, 2011)

7. ## Re: Java Binary Tree (Beginners)?

Originally Posted by helloworld922
Only if the assumption I said holds. Actually, the assumption you're making is:
.........
I think you're right.

So, I changed my code so that the base case meets your requirement.
So my code right???

```// returns the weight of node v
static int weight(BinaryTree t, Node v)
if t.size == 0 then 	// base case: if BinaryTree t is an empty tree
return 0
else

if not(t.hasLeft(v) or t.hasRight(v)) then 	// base case: if Node v has no left child and right child, it means Node v is an external node.
return v.element
else
return weight(t, t.left(v)) + weight(t, t.right(v))```

So my code right???

8. ## Re: Java Binary Tree (Beginners)?

mmm, not quite.

Now you're making the assumption that the node must either not have any children, or it must have both a left and right child.

You must check for each child individually and add the weight from each node separately. The pseudo-code I provided is basically a line-by-line of what the code should do.

9. ## The Following User Says Thank You to helloworld922 For This Useful Post:

IAmHere (June 19th, 2011)

10. ## Re: Java Binary Tree (Beginners)?

```if t.hasALeft(v) then
{
left = t.left(v)
}

return weight(t, left) + weight(t, right)

if t.hasARight(v) then
{
right = t.Right(v)
}```

Would this be right?
It look right to me.