# RObservations # 19: Breadth-first search for Binary Trees

**r – bensstats**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

# 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.

## Want to see more of my content?

Be sure to subscribe and never miss an update!

**leave a comment**for the author, please follow the link and comment on their blog:

**r – bensstats**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.