Introduction

In my last blog I shared how to do a depth-first search in R by using R6 classes. In this short blog I’m going to show how to do a breadth-first search.

Breadth-first search: A brief explination.

In contrast to a depth-first search which traverses a tree by going to the children farthest down on the tree before proceeding up, a breadth first search starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored (Thank you Wikipedia, I copied that explanation verbatim).

So for the tree below the order of nodes visiting from the root node would be a > b > c > d > e > f.

            a
           / \
          b   c
         / \   \
        d   e   f

R Code

For setting up the tree I will use the same R6 objects I created in my last blog:

# Binary tree
library(R6)

node <- R6Class("Node",
                list(
                  val=NULL,
                  left=NULL,
                  right=NULL,
                  initialize= function(val=NULL,
                                       left=NULL,
                                       right=NULL){
                    self$val<- val
                    self$left<- left
                    self$right<-right
                  }
                )
                )

# Nodes
a<-node$new(val='a')
b <- node$new(val='b')
c<-node$new(val='c')
d <- node$new(val='d')
e<-node$new(val='e')
f <- node$new(val='f')

# Children
a$left<- b
a$right<-c
b$left<-d
b$right<-e
c$right<-f

To do the breadth-first search, the following function is used:

# Breadth-First
# Time complexity O(n)
# Space complexity O(n)

breadthFirstValues<- function(root){
queue<-c(root)
# Empty values list
values <- c()
while (length(queue)> 0){
  # Current value being evaluated
  current<-queue[[1]]
  values<-append(values,current$val)

  # Add items to the queue- (from left to right)

  if(!is.null(current$left$val)){
    queue<- append(queue,current$left)
  }
  if(!is.null(current$right$val)){
    queue<- append(queue,current$right)
  }
  # Remove first evaluated item from the queue
  queue<-queue[-1]
}
values
}

The breadth first search is thus:

breadthFirstValues(a)


## [1] "a" "b" "c" "d" "e" "f"

Conclusion

This code is inspired by Alvin’s solution in FreecodeCamp’s video on binary search algorithms. I wrote about my particular stylistic criticisms regarding my code in my last blog, and for this case it would similarly apply.