Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

MMM24's blog

Looping through a tree
By MMM24, history, 9 years ago, In English

Hi all. I have the following code

void f(int x)
{
  if(x<0||x>10000) return ;
  f(x-1);
  f(2*x);
}

When this code is executed it will start from left (x-1) untill he reach the last element and then go to the right and so on

How ever i want it to proceed from up to down like in the picture

Any helps. regards.

  • Vote: I like it
  • -5
  • Vote: I do not like it

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

you can use BFS instead of DFS. It means you can have a queue that put sub-states of current state in it, and every time you have done with current state, you should pick a new state from the queue. (for more details, google it :) )

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

    thanks for your reply , BFS is great solution to this problem but i still want to know if there is a way to do it with DFS :)

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

      also you can use depth controlled DFS, I mean you can use a factor depth in your function and prevent to go beyond this limit, so you can check all the possible states at desired level D from the root. By increasing this limit (D), you can search whole the graph using DFS but similar to BFS.

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

        i start to understand a bit , you mean add a parametre to the function that prevent it to go in one direction . Right ?? Can you provide a code ??

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          not exactly one direction, just one level!

          void DFS(int u, int depth, int current_level) {
	visit[u] = true;
	if (current_level == depth) {
		// we have reached the desired level
		return;
	}
	for (int v : adjacent[u]) {
		// go and check the adjacents of current node
		DFS(v, depth, current_level + 1);
	}
}

          so you can call DFS by increasing the value of depth. It gives you the advantage of BFS.

          → Reply