wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Binary Tree algorithm Solution required
        
(Message started by: suriait2000 on Apr 20^th, 2008, 8:19pm)

Title: Binary Tree algorithm Solution required
Post by suriait2000 on Apr 20^th, 2008, 8:19pm

Hi All,
Please help me to give hint or solution of algorithm given below realted to Binary Tree.
Problem:
Assume that you are given a binary tree such that each node only contains pointers to its left and its right tree(i.e there are no back pointers back to the parent) Assume that the leaves of the binary tree have been assigned values and the all internal nodes have undefined values (you cannot assume that some special value such as -32.767 means that no value is defined).
Write a function sum_up_nodes that fills in each internal node with a value = sum of its childern. The interface of the function could be as follows
Void sum_up_nodes(Tree tree)
Please give implementation in Java if possible.
Expecting speedy response.
Thank you
Suri

Title: Re: Binary Tree algorithm Solution required
Post by towr on Apr 21^st, 2008, 12:44am

hints:
[hide]-use recursion

-for leaf nodes both children are null.

-for each node sum the value of its child nodes (after determining their value if their not leaves)[/hide]

Title: Re: Binary Tree algorithm Solution required
Post by suriait2000 on Apr 21^st, 2008, 5:46pm

Thanks for reply.
Please give me solution on urgent basis.
Thanks
Suri

Title: Re: Binary Tree algorithm Solution required
Post by towr on Apr 22^nd, 2008, 12:28am

Homework? I can't imagine why it'd be 'urgent' otherwise.. Regardless, I don't know enough java to implement it :P
But if you give it a try, I might be able to point out possible mistakes in the code. (Modifying code in an unknown programming language is easier than writing something new in it).

Title: Re: Binary Tree algorithm Solution required
Post by SMQ on Apr 22^nd, 2008, 5:57am

Eh, why not. ;)

public void sumUpNode(TreeNode node) { if (node.getLeft() != null) { sum_up_node(node.getLeft()); node.setValue(node.getLeft().getValue()); } if (node.getRight() != null) { sum_up_node(node.getRight()); if (node.getLeft() != null) { node.setValue(node.getValue() + node.getRight().getValue()); } else { node.setValue(node.getRight().getValue()); } } } public void sum_up_nodes(Tree tree) { if (tree != null && tree.getRootNode() != null) { sumUpNode(tree.getRootNode()); } }

--SMQ

Title: Re: Binary Tree algorithm Solution required
Post by Grimbal on Apr 22^nd, 2008, 7:16am

Assuming the values are int's:

public int sum_up_nodes(TreeNode node) { if (node == null) return 0; if (node.getLeft() != null || node.getRight() != null) node.setValue(sum_up_nodes(node.getLeft()) + sum_up_nodes(node.getRight())); return node.getValue(); }

[edit]Indeed, it was sum_up_nodes. The int return value doesn't prevent it to be used like a void procedure, so I thought it is acceptable.[/edit]

Title: Re: Binary Tree algorithm Solution required
Post by Hippo on Apr 23^rd, 2008, 11:37am

I like the Grimbal's one. Except it seems to me java will not consider sumUpNode and sum_up_nodes to be the same indentifier ;)

BTW: Is the 2nd condition needed?

Title: Re: Binary Tree algorithm Solution required
Post by SMQ on Apr 23^rd, 2008, 1:38pm

I think he (Grimbal) is just replacing the first function in my two-function approach. Only wish I'd been on-the-ball enough to catch that sumUpNode didn't have to be void just because sum_up_nodes was... his way is indeed much cleaner.

--SMQ

Title: Re: Binary Tree algorithm Solution required
Post by Grimbal on Apr 23^rd, 2008, 2:49pm

I corrected my post.

I actually thought of an int sum_up_node, which is stretching the requirements a bit.