Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

0-jij-0's blog

By 0-jij-0, history, 5 months ago, In English,

Hello everyone,

Consider the following problem: given a tree of N node (N <= 10^5), find the size of all subtrees of the tree, assuming the root of the tree is at node 0(or 1).

This problem is fairly easy using recursive DFS traversal of the tree, but as every recursive approach we might get a stack overflow exception if we run it on a list of 10^5 nodes for example.

So my question is: Is it possible to compute these values iteratively (ie. using iterative DFS or possibly BFS or some other approach) instead of recursively?

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it