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

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.

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

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.