Author |
Topic: Tree problem (iterative version) (Read 857 times) |
|
amit_csus
Newbie
Gender: 
Posts: 6
|
 |
Tree problem (iterative version)
« on: Aug 26th, 2010, 2:35am » |
 Quote  Modify
|
Given a tree (Note not binary it may have many children).
The value of nodes in the tree are integers. You need to modify the tree such that the value of each parent = sum (value of all children) + parent.value
Note the recursive version is simple. But how can the same be done using iteration
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Tree problem (iterative version)
« Reply #1 on: Aug 26th, 2010, 2:55am » |
Quote Modify
|
I think something like the following would work, though it is probably not the most memory-efficient way to do it
Pseudo Code:node* S[#nodes]
S[0]=root;
j=1
for(i=0; i < #nodes; i++)
{
for(k=0; k < S[i]->#children; k++)
S[j++]=S[i]->child[k];
}
for(i=#nodes-1; i >=0 i--)
{
for(k=0; k < S[i]->#children; k++)
S[i]->val+=S[i]->child[k]->val;
} |
|
S will contain all the nodes in breadth first order, so when you modify the nodes in the array from back to front, all the child nodes will have the right value when you reach the parent. (Instead of an array you could also use a doubly-linked list, that way you don't need to know the number of nodes at the start.)
|
| « Last Edit: Aug 26th, 2010, 2:57am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Tree problem (iterative version)
« Reply #2 on: Aug 26th, 2010, 9:41am » |
Quote Modify
|
One can also do a Depth First Traversal and whenever a node gets pushed onto the stack, just propagate : the pushed_node's value, the pushed_node's depth and the propagated_node's depth; from pushed_node to root.
I guess this will use ~ O(log |V|) memory at any point and time complexity of O((|V| + |E|)*log|V|).
Edit2 : The time can be improved to O(|V| + |E| + |L|*log|V|), where |L| is the # of leaf nodes.
-- AI
P.S. -> I guess this one improves on space, but sacrifices on time.
|
| « Last Edit: Aug 26th, 2010, 10:16am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print