Performing Breadth First Search recursively

Question

Let s say you wanted to implement a breadth-first search of a binary tree recursively  How would you go about it   Is it possible using only the call-stack as auxiliary storage

User · Answer

Here s a python implementation   graph     A     B    C              B     C    D              C     D              D     C              E     F              F     C     def bfs paths  goal       if not paths          raise StopIteration      new paths          for path in paths          if path -1     goal              yield path          last   path -1          for neighbor in graph last               if neighbor not in path                  new paths append path    neighbor       yield from bfs new paths  goal    for path in bfs    A      D        print path

User · Answer

I would like to add my cents to the top answer in that if the language supports something like generator  bfs can be done co-recursively    To begin with   Tanzelax s answer reads      Breadth-first traversal traditionally uses a queue  not a stack  The nature of a queue and a stack are pretty much opposite  so trying to use the call stack  which is a stack  hence the name  as the auxiliary storage  a queue  is pretty much doomed to failure   Indeed  ordinary function call s stack won t behave like a normal stack  But generator function will suspend the execution of function so it gives us the chance to yield next level of nodes  children without delving into deeper descendants of the node   The following code is recursive bfs in Python   def bfs root     yield root   for n in bfs root       for c in n children        yield c   The intuition here is    bfs first will return the root as first result suppose we already have the bfs sequence  the next level of elements in bfs is the immediate children of previous node in the sequence repeat the above two procedures

User · Answer

If you use an array to back the binary tree  you can determine the next node algebraically  if i is a node  then its children can be found at 2i   1  for the left node  and 2i   2  for the right node   A node s next neighbor is given by i   1  unless i is a power of 2  Here s pseudocode for a very naive implementation of breadth first search on an array backed binary search tree  This assumes a fixed size array and therefore a fixed depth tree  It will look at parentless nodes  and could create an unmanageably large stack   bintree-bfs bintree  elt  i      if  i    LENGTH          return false      else if  bintree i     elt          return true      else          return bintree-bfs bintree  elt  i 1

User · Answer

Here is a BFS recursive traversal Python implementation  working for a graph with no cycle   def bfs recursive level                 params level  List lt Node gt  containing the node for a specific level              next level          for node in level          print node value          for child node in node adjency list              next level append child node      if len next level     0          bfs recursive next level    class Node      def   init   self  value           self value   value         self adjency list

User · Answer

I couldn t find a way to do it completely recursive  without any auxiliary data-structure   But if the queue Q is passed by reference  then you can have the following silly tail recursive function   BFS Q      if   Q   gt  0       v  lt - Dequeue Q       Traverse v       foreach w in children v          Enqueue Q  w            BFS Q

User · Answer

I m assuming that this is just some kind of thought exercise  or even a trick homework interview question  but I suppose I could imagine some bizarre scenario where you re not allowed any heap space for some reason  some really bad custom memory manager  some bizarre runtime OS issues   while you still have access to the stack      Breadth-first traversal traditionally uses a queue  not a stack   The nature of a queue and a stack are pretty much opposite  so trying to use the call stack  which is a stack  hence the name  as the auxiliary storage  a queue  is pretty much doomed to failure  unless you re doing something stupidly ridiculous with the call stack that you shouldn t be   On the same token  the nature of any non-tail recursion you try to implement is essentially adding a stack to the algorithm   This makes it no longer breadth first search on a binary tree  and thus the run-time and whatnot for traditional BFS no longer completely apply   Of course  you can always trivially turn any loop into a recursive call  but that s not any sort of meaningful recursion   However  there are ways  as demonstrated by others  to implement something that follows the semantics of BFS at some cost   If the cost of comparison is expensive but node traversal is cheap  then as  Simon Buchan did  you can simply run an iterative depth-first search  only processing the leaves   This would mean no growing queue stored in the heap  just a local depth variable  and stacks being built up over and over on the call stack as the tree is traversed over and over again   And as  Patrick noted  a binary tree backed by an array is typically stored in breadth-first traversal order anyway  so a breadth-first search on that would be trivial  also without needing an auxiliary queue

User · Answer

I think this can be done using pointers  without using any QUEUE  Basically we are maintaining two pointers at any point  one is pointing to the parents  the other is pointing to the children to be processed   linkedlist to all which have been processed   Now you simply assign the pointer of the child  amp  when parent processing finishes you just make the child to be parent for processing next level following is my code     Tree Node struct Node       int val      Node  left      Node  right      Node  next       Node     val 0   left NULL   right NULL   next NULL          Node int  val    val  val   left NULL   right NULL   next NULL          Node int  val  Node   left  Node   right  Node   next            val  val   left  left   right  right   next  next                Algorightm       void LevelTraverse Node  parent Node  chidstart Node  childend            if  parent  amp  amp   chidstart  return      we processed everything                  if  parent  amp  amp  chidstart     finished processing last level             parent chidstart chidstart childend NULL     assgin child to parent for processing next level             LevelTraverse parent chidstart childend            else if parent  amp  amp   chidstart      This is new level first node tobe processed             Node  temp parent  parent parent- gt next              if temp- gt left    childend chidstart temp- gt left                if chidstart                   if temp- gt right    childend- gt next temp- gt right  childend temp- gt right                 else                  if temp- gt right    childend chidstart temp- gt right                              LevelTraverse parent chidstart childend            else if parent  amp  amp  chidstart     we are in mid of some level processing             Node  temp parent  parent parent- gt next              if temp- gt left    childend- gt next temp- gt left  childend temp- gt left                if temp- gt right    childend- gt next temp- gt right  childend temp- gt right                LevelTraverse parent chidstart childend                      Driver code       Node  connect Node  root            if  root  return NULL          Node  parent  Node  childs   childe  parent childs childe NULL          parent root          LevelTraverse parent  childs  childe           return root

User · Answer

A simple BFS and DFS recursion in Java  Just push offer the root node of the tree in the stack queue and call these functions   public static void breadthFirstSearch Queue queue         if  queue isEmpty            return       Node node    Node  queue poll         System out println node              if  node right    null          queue offer node right        if  node left    null          queue offer node left        breadthFirstSearch queue      public static void depthFirstSearch Stack stack         if  stack isEmpty            return       Node node    Node  stack pop         System out println node              if  node right    null          stack push node right        if  node left    null          stack push node left        depthFirstSearch stack

User · Answer

Let v be the starting vertex  Let G be the graph in question  The following is the pseudo code without using queue  Initially label v as visited as you start from v BFS G v      for all adjacent vertices w of v in G          if vertex w is not visited              label w as visited     for all adjacent vertices w of v in G          recursively call BFS G w

User · Answer

Here s a Scala 2 11 4 implementation of recursive BFS  I ve sacrificed tail-call optimization for brevity  but the TCOd version is very similar  See also  snv s post   import scala collection immutable Queue  object RecursiveBfs     def bfs A  tree  Tree A   target  A   Boolean         bfs Queue tree   target         private def bfs A  forest  Queue Tree A    target  A   Boolean         forest dequeueOption exists         case  E  tail    gt  bfs tail  target        case  Node value            if value    target   gt  true       case  Node    l  r   tail    gt  bfs tail enqueue List l  r    target               sealed trait Tree  A    case class Node  A  data  A  left  Tree A   right  Tree A   extends Tree A    case object E extends Tree Nothing

User · Answer

I found a very beautiful recursive  even functional  Breadth-First traversal related algorithm  Not my idea  but i think it should be mentioned in this topic   Chris Okasaki explains his breadth-first numbering algorithm from ICFP 2000 at http   okasaki blogspot de 2008 07 breadth-first-numbering-algorithm-in html very clearly with only 3 pictures   The Scala implementation of Debasish Ghosh  which i found at http   debasishg blogspot de 2008 09 breadth-first-numbering-okasakis html  is   trait Tree  T  case class Node  T  data  T  left  Tree T   right  Tree T   extends Tree T  case object E extends Tree Nothing   def bfsNumForest T  i  Int  trees  Queue Tree T     Queue Tree Int         if  trees isEmpty  Queue Empty   else       trees dequeue match         case  E  ts    gt          bfsNumForest i  ts  enqueue Tree Int   E        case  Node d  l  r   ts    gt          val q   ts enqueue l  r          val qq   bfsNumForest i 1  q          val  bb  qqq    qq dequeue         val  aa  tss    qqq dequeue         tss enqueue org dg collection BFSNumber Tree Int   Node i  aa  bb                def bfsNumTree T  t  Tree T    Tree Int        val q   Queue Empty enqueue Tree T   t    val qq   bfsNumForest 1  q    qq dequeue  1

User · Answer

I had to implement a heap traversal which outputs in a BFS order  It isn t actually BFS but accomplishes the same task   private void getNodeValue Node node  int index  int   array        array index    node value      index    index 2  1       Node left   node leftNode      if  left  null  getNodeValue left index array       Node right   node rightNode      if  right  null  getNodeValue right index 1 array      public int   getHeap         int   nodes   new int size       getNodeValue root 0 nodes       return nodes

User · Answer

The following seems pretty natural to me  using Haskell  Iterate recursively over levels of the tree  here I collect names into a big ordered string to show the path through the tree    data Node   Node  name    String  children     Node   aTree   Node  r   Node  c1   Node  gc1   Node  ggc1       Node  gc2        Node  c2   Node  gc3       Node  c3       breadthFirstOrder x   levelRecurser  x      where levelRecurser level   if length level    0                                 then                                    else concat  name node          node  lt - level     levelRecurser  concat  children node   node  lt - level

User · Answer

BFS for a binary  or n-ary  tree can be done recursively without queues as follows  here in Java    public class BreathFirst        static class Node           Node int value                this value  0                     Node int value  int nChildren                this value   value              this children   new Node nChildren                     int value          Node   children             static void breathFirst Node root  Consumer lt   super Node gt  printer            boolean keepGoing   true          for  int level   0  keepGoing  level                  keepGoing   breathFirst root  printer  level                        static boolean breathFirst Node node  Consumer lt   super Node gt  printer  int depth            if  depth  lt  0    node    null  return false          if  depth    0                printer accept node               return true                    boolean any   false          for  final Node child   node children                any    breathFirst child  printer  depth - 1                     return any            An example traversal printing numbers 1-12 in ascending order   public static void main String    args                      1                                     2   3   4                                     5   6       7  8                                  9  10         11  12      Node root   new Node 1  3       root children 0    new Node 2  2       root children 1    new Node 3       root children 2    new Node 4  2       root children 0  children 0    new Node 5  2       root children 0  children 1    new Node 6       root children 2  children 0    new Node 7  2       root children 2  children 1    new Node 8       root children 0  children 0  children 0    new Node 9       root children 0  children 0  children 1    new Node 10       root children 2  children 0  children 0    new Node 11       root children 2  children 0  children 1    new Node 12        breathFirst root  n - gt  System out println n value

User · Answer

Following is my code for completely recursive implementation of breadth-first-search of a bidirectional graph without using loop and queue    public class Graph       public int V         public LinkedList lt Integer gt  adj         Graph int v                V   v          adj   new LinkedList v           for  int i 0  i lt v    i              adj i    new LinkedList lt  gt                void addEdge int v int w                adj v  add w           adj w  add v              public LinkedList lt Integer gt  getAdjVerted int vertex                return adj vertex              public String toString                 String s                for  int i 0 i lt adj length i                          s   s    n  i   -- gt    adj i                      return s             BFS IMPLEMENTATION  public static void recursiveBFS Graph graph  int vertex boolean visited    boolean isAdjPrinted                  if   visited vertex                         System out print vertex                    visited vertex    true                     if  isAdjPrinted vertex                         isAdjPrinted vertex    true              List lt Integer gt  adjList   graph getAdjVerted vertex               printAdjecent graph  adjList  visited  0 isAdjPrinted                        public static void recursiveBFS Graph graph  List lt Integer gt  vertexList  boolean visited    int i  boolean isAdjPrinted                  if  i  lt  vertexList size                          recursiveBFS graph  vertexList get i   visited  isAdjPrinted               recursiveBFS graph  vertexList  visited  i 1  isAdjPrinted                        public static void printAdjecent Graph graph  List lt Integer gt  list  boolean visited    int i  boolean isAdjPrinted                  if  i  lt  list size                          if   visited list get i                                  System out print list get i                        visited list get i     true                            printAdjecent graph  list  visited  i 1  isAdjPrinted                     else                       recursiveBFS graph  list  visited  0  isAdjPrinted

User · Answer

The dumb way   template lt typename T gt  struct Node   Node  left  Node  right  T value      template lt typename T  typename P gt  bool searchNodeDepth Node lt T gt   node  Node lt T gt    result  int depth  P pred        if   node  return false      if   depth            if  pred node- gt value                  result   node                    return true            --depth      searchNodeDepth node- gt left  result  depth  pred       if    result          searchNodeDepth node- gt right  result  depth  pred       return true     template lt typename T  typename P gt  Node lt T gt   searchNode Node lt T gt   node  P pred        Node lt T gt   result   NULL      int depth   0      while  searchNodeDepth node   amp result  depth  pred   amp  amp   result            depth      return result     int main            a c   f         b   e           d     Node lt char  gt          a     NULL  NULL   A             c     NULL  NULL   C             b      amp a   amp c   B             f     NULL  NULL   F             e     NULL   amp f   E             d      amp b   amp e   D          Node lt char  gt   found   searchNode  amp d     char  value  - gt  bool           printf   s n   value           return  strcmp  char  value   F                 printf  found   s n   found- gt value        return 0

User · Answer

The following method used a DFS algorithm to get all nodes in a particular depth - which is same as doing BFS for that level  If you find out depth of the tree and do this for all levels  the results will be same as a BFS   public void PrintLevelNodes Tree root  int level        if  root    null            if  level    0                Console Write root Data               return                    PrintLevelNodes root Left  level - 1           PrintLevelNodes root Right  level - 1            for  int i   0  i  lt  depth  i          PrintLevelNodes root  i       Finding depth of a tree is a piece of cake   public int MaxDepth Tree root        if  root    null            return 0        else           return Math Max MaxDepth root Left   MaxDepth root Right     1

User · Answer

Here is a JavaScript Implementation that fakes Breadth First Traversal with Depth First recursion  I m storing the node values at each depth inside an array  inside of a hash  If a level already exists we have a collision   so we just push to the array at that level  You could use an array instead of a JavaScript object as well since our levels are numeric and can serve as array indices  You can return nodes  values  convert to a Linked List  or whatever you want  I m just returning values for the sake of simplicity   BinarySearchTree prototype breadthFirstRec   function          var levels            var traverse   function current  depth            if   current  return null          if   levels depth   levels depth     current value           else levels depth  push current value           traverse current left  depth   1           traverse current right  depth   1               traverse this root  0       return levels       var bst   new BinarySearchTree    bst add 20  22  8  4  12  10  14  24   console log  Recursive Breadth First     bst breadthFirstRec       Recursive Breadth First       0     20       1     8  22       2     4  12  24       3     10  14          Here is an example of actual Breadth First Traversal using an iterative approach   BinarySearchTree prototype breadthFirst   function          var result               queue               current   this root       if   current  return null      queue push current        while  current   queue shift              result    current value                current left  amp  amp  queue push current left           current right  amp  amp  queue push current right             return result      console log  Breadth First     bst breadthFirst       Breadth First   20 8 22 4 12 24 10 14

User · Answer

Here is short Scala solution     def bfs nodes  List Node    List Node          if  nodes nonEmpty          nodes    bfs nodes flatMap   children         else         List empty             Idea of using return value as accumulator is well suited  Can be implemented in other languages in similar way  just make sure that your recursive function process list of nodes   Test code listing  using  marco test tree    import org scalatest FlatSpec  import scala collection mutable  class Node val value  Int       private val  children  mutable ArrayBuffer Node    mutable ArrayBuffer empty    def add child  Node   Unit    children    child    def children    children toList    override def toString  String   s  value     class BfsTestScala extends FlatSpec                    1                                 2   3   4                                 5   6       7  8                              9  10         11  12   def tree    Node         val root   new Node 1      root add new Node 2       root add new Node 3       root add new Node 4       root children 0  add new Node 5       root children 0  add new Node 6       root children 2  add new Node 7       root children 2  add new Node 8       root children 0  children 0  add new Node 9       root children 0  children 0  add new Node 10       root children 2  children 0  add new Node 11       root children 2  children 0  add new Node 12       root        def bfs nodes  List Node    List Node          if  nodes nonEmpty          nodes    bfs nodes flatMap   children         else         List empty               BFS  should  work  in       println bfs List tree              Output   List 1  2  3  4  5  6  7  8  9  10  11  12

User · Answer

I have made a program using c   which is working in joint and disjoint graph too         include  lt queue gt   include  iostream   include  vector   include  queue   using namespace std   struct Edge       int source destination      class Graph      int V      vector lt vector lt int gt  gt  adjList  public       Graph vector lt Edge gt  edges int V           this- gt V   V          adjList resize V           for auto i   edges               adjList i source  push back i destination                      adjList i destination  push back i source                       void BFSRecursivelyJoinandDisjointtGraphUtil vector lt bool gt   amp discovered  queue lt int gt   amp q       void BFSRecursivelyJointandDisjointGraph int s       void printGraph          void Graph    printGraph         for  int i   0  i  lt  this- gt adjList size    i                  cout  lt  lt  i  lt  lt    --            for  int v   this- gt adjList i               cout  lt  lt  - gt   lt  lt  v  lt  lt               cout  lt  lt  endl            void Graph   BFSRecursivelyJoinandDisjointtGraphUtil vector lt bool gt   amp discovered  queue lt int gt   amp q        if  q empty            return      int v   q front        q pop        cout  lt  lt  v  lt  lt          for  int u   this- gt adjList v                 if   discovered u                         discovered u    true              q push u                       BFSRecursivelyJoinandDisjointtGraphUtil discovered  q       void Graph   BFSRecursivelyJointandDisjointGraph int s        vector lt bool gt  discovered V  false       queue lt int gt  q       for  int i   s  i  lt  V  i              if  discovered i     false                        discovered i    true              q push i               BFSRecursivelyJoinandDisjointtGraphUtil discovered  q                      int main          vector lt Edge gt  edges                                      0  1    0  2    1  2    2  0    2 3   3 3                      int V   4      Graph graph edges  V         graph printGraph        graph BFSRecursivelyJointandDisjointGraph 2       cout  lt  lt    n           edges                  0 4   1 2   1 3   1 4   2 3   3 4              Graph graph2 edges 5        graph2 BFSRecursivelyJointandDisjointGraph 0       return 0

User · Answer

include  lt bits stdc   h gt  using namespace std   define Max 1000  vector  lt int gt  adj Max   bool visited Max    void bfs recursion utils queue lt int gt  amp  Q        while  Q empty              int u   Q front            visited u    true          cout  lt  lt  u  lt  lt  endl          Q pop            for int i   0  i  lt   int adj u  size      i                int v   adj u  i               if  visited v                   Q push v   visited v    true                    bfs recursion utils Q            void bfs recursion int source  queue  lt int gt  amp  Q        memset visited  false  sizeof visited       Q push source       bfs recursion utils Q      int main void        queue  lt int gt  Q      adj 1  push back 2       adj 1  push back 3       adj 1  push back 4        adj 2  push back 5       adj 2  push back 6        adj 3  push back 7        bfs recursion 1  Q       return 0

User · Answer

C  implementation of recursive breadth-first search algorithm for a binary tree   Binary tree data visualization  IDictionary lt string  string   gt  graph   new Dictionary lt string  string   gt          A   new      B    C           B   new      D    E           C   new      F    G           E   new      H        void Main         var pathFound   BreadthFirstSearch  A    H   new string 0        Console WriteLine pathFound       A  B  E  H       var pathNotFound   BreadthFirstSearch  A    Z   new string 0        Console WriteLine pathNotFound            IEnumerable lt string gt  BreadthFirstSearch string start  string end  IEnumerable lt string gt  path        if  start    end                return path Concat new     end                if   graph ContainsKey start     return new string 0              return graph start  SelectMany letter   gt  BreadthFirstSearch letter  end  path Concat new     start           If you want algorithm to work not only with binary-tree but with graphs what can have two and more nodes that points to same another node you must to avoid self-cycling by holding list of already visited nodes  Implementation may be looks like this   Graph data visualization  IDictionary lt string  string   gt  graph   new Dictionary lt string  string   gt          A   new      B    C           B   new      D    E           C   new      F    G    E           E   new      H        void Main         var pathFound   BreadthFirstSearch  A    H   new string 0   new List lt string gt          Console WriteLine pathFound       A  B  E  H       var pathNotFound   BreadthFirstSearch  A    Z   new string 0   new List lt string gt          Console WriteLine pathNotFound            IEnumerable lt string gt  BreadthFirstSearch string start  string end  IEnumerable lt string gt  path  IList lt string gt  visited        if  start    end                return path Concat new     end                if   graph ContainsKey start     return new string 0           return graph start  Aggregate new string 0    acc  letter    gt                if  visited Contains letter                         return acc                     visited Add letter            var result   BreadthFirstSearch letter  end  path Concat new     start     visited           return acc Concat result  ToArray

[algorithm] Performing Breadth First Search recursively

Examples related to algorithm

Examples related to breadth-first-search