0-jij-0's blog

Iterative BFS/DFS
By 0-jij-0, history, 5 years 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?

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

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Implement your own call stack and simulate recursion with a while loop. I'll leave you to figure out how, it's a good exercise.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Although this was not what I was looking for, but I really liked the idea. Thank you!

    → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Alternatively to implementing a callstack, a solution specific to this problem is as follows: We can do it LITERALLY bottom up! The idea is to propagate subtree size from the bottom (the leaves) all the way to the root. First, label each node with the number of "kids" it has (can be done using a simple queue BFS),and label each node with the "value" 1. Then reverse the entire tree. Push all the nodes with kids=0 into a list, those, in the original tree, are the leaves. Now they will act as independent sources. Iterate over all the elements in the list, and add the "value" of each node to all its childrens' values, and decrement the "kids" label by 1 for each of the children. Remove the node being processed from the list, and add any of its kids who have kids=0 now, meaning all their subtrees have been processed, and the node is complete and ready to propagate upwards.

→ Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it +13 Vote: I do not like it

Run a BFS, which would calculate parent of every node, and depth of every node.

Initialize all sizes to 1.

Sort nodes by their depth: start processing from the deepest nodes (leaves).

And by "process", I mean: execute size[parent[v]] += size[v].

Edit: you don't have to use O(N log N) sort, you can have a linear counting sort, since all the depths are so small. Like, have a: vector<int> nodes_of_depth_x[N]

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The proper and simple way to do this would be to use a stack.
More ways to do this:
| Go through every node n times and updating each node that hasn't been updated yet in O(n^2)
| Keep a linked list of every node that hasn't been updated yet in O(n*height)

→ Reply