Author |
Topic: Binary Tree algorithm Solution required (Read 515 times) |
|
suriait2000
Newbie
Posts: 2
|
 |
Binary Tree algorithm Solution required
« on: Apr 20th, 2008, 8:19pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Binary Tree algorithm Solution required
« Reply #1 on: Apr 21st, 2008, 12:44am » |
Quote Modify
|
hints:
-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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
suriait2000
Newbie
Posts: 2
|
|
Re: Binary Tree algorithm Solution required
« Reply #2 on: Apr 21st, 2008, 5:46pm » |
Quote Modify
|
Thanks for reply.
Please give me solution on urgent basis.
Thanks
Suri
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary Tree algorithm Solution required
« Reply #3 on: Apr 22nd, 2008, 12:28am » |
Quote Modify
|
Homework? I can't imagine why it'd be 'urgent' otherwise.. Regardless, I don't know enough java to implement it 
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Binary Tree algorithm Solution required
« Reply #4 on: Apr 22nd, 2008, 5:57am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Binary Tree algorithm Solution required
« Reply #5 on: Apr 22nd, 2008, 7:16am » |
Quote Modify
|
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]
|
| « Last Edit: Apr 23rd, 2008, 2:47pm by Grimbal » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Binary Tree algorithm Solution required
« Reply #6 on: Apr 23rd, 2008, 11:37am » |
Quote Modify
|
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?
|
| « Last Edit: Apr 23rd, 2008, 11:38am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Binary Tree algorithm Solution required
« Reply #7 on: Apr 23rd, 2008, 1:38pm » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Binary Tree algorithm Solution required
« Reply #8 on: Apr 23rd, 2008, 2:49pm » |
Quote Modify
|
I corrected my post.
I actually thought of an int sum_up_node, which is stretching the requirements a bit.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print