Iterative BFS/DFS

Правка en1, от 0-jij-0, 2019-10-24 11:07:31

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?

Теги graph, dfs/bfs, iterative

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский 0-jij-0 2019-10-24 11:07:31 554 Initial revision (published)