CODEWITHSUNDEEP
algorithmtreegraph-theorybreadth-first-search
angel_30
angel_30

Reputation: 1

Modified BFS tree traversal

I was trying to implement a tree traversal algorithm similar to BFS, but with a small modification. Whenever we are jumping to the next line, we should start from the nearest child (child of last node in the row) instead of the farthest node of next row. How can I modify the BFS code to achieve this?

This is the original BFS code:

   public void bfs()
   {
      // BFS uses Queue data structure

      Queue q = new LinkedList();

      q.add(rootNode);
      visited[rootNode] = true;

      printNode(rootNode);

      while( !q.isEmpty() )
      {
         int n, child;

         n = (q.peek()).intValue();

         child = getUnvisitedChildNode(n);    // Returns -1 if no unvisited niode left     

         if ( child != -1 )
         {  // Found an unvisted node 

            visited[child] = true;        // Mark as visited

            printNode(child);

            q.add(child);      // Add to queue 
         }
         else
         {
            q.remove();                  // Process next node
         }
      }
   }

This is how my desired modified BFS should work:

enter image description here

enter image description here

Upvotes: 1

Views: 401

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

Have 2 stacks - one for the current level, one for the next level.

Do peek / pop from the current level and push to the next level. If the current level is empty, swap the two stacks (so the next level becomes the current level and vice versa).

It would look something like this:
(like your code but with q replaced by current and next, and swapping the two)

Stack current, next;
// ...
current.push(rootNode);
while (!current.isEmpty() || !next.isEmpty())
{
   if (current.isEmpty())
   {
      current = next;
      next.clear();
   }
   int n = current.peek();
   // ...
   next.add(child);
   // ...
   current.pop();
}

getUnvisitedChildNode would also need to change (since it currently presumably forces a left-to-right direction on an individual node). One option would be to pass a direction down to decide whether to return the next child from the left or right side (which you invert when swapping next and current).

It is possible to do this without changing getUnvisitedChildNode, but would require some "ugly" code - the basic idea would be to call getUnvisitedChildNodein a loop until you have all children of some given node, throwing all of those children into an array (without processing i.e. printing them), then choosing the direction in which to process them using a similar direction variable as described above.

If you already have access to the children array, you can probably just loop over that directly from either the left or right.

Upvotes: 1

Related Questions