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

Code :

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

Re: Java Binary Tree (Beginners)?

Quote:

Code Pseudo:

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.

Re: Java Binary Tree (Beginners)?

Quote:

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?

Thank you for your help.

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.

Re: Java Binary Tree (Beginners)?

Quote:

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

Code :

// 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???

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.

Re: Java Binary Tree (Beginners)?

Code :

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.