# RObservations #18: Depth-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

The more I use R, the more I am convinced that you can do anything with it. Recently, I checked out FreeCodeCamp’s video “Binary Tree Algothritms for Technical Interviews” and was told that I can write the code in any language I want. While Alvin used Javascript, I decided to follow along with R.

In this blog I am going to share my code for preforming a “depth-first search” algorithm for a binary tree.

# Depth-first search- a brief explination.

With the help if Wikipedia, the depth-first search is a algorithm for traversing across tree data structures. It starts with the root node and explores as far as possible along each branch.

For the case of a tree which looks like this:

a / \ b c / \ \ d e f

Using the depth-first algorithm, the order of visiting nodes would be a > b > d > e > c > f.

# Using R

Technically, base R does not intuitively have the availability to do OOP and to my knowledge, your only option is to use R6 objects which were developed by the team at RStudio and is available in the R6 package. For setting up the above tree, the code used for setting up the nodes is:

library(R6) # Node Constructor 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 } ) ) # Giving each node a value 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') a$left<- b a$right<-c b$left<-d b$right<-e c$right<-f

The code for preforming a depth first search is:

# Depth First algorithm # Time complexity is O(n) # Space complexity is O(n) depthFirstValues <- function(root){ # create a stack stack <-c(root) while (length(stack)> 0){ # Don't have a pop method so this needs to be done # in two steps # Need to index 1 on the list to select the node. current <- stack[length(stack)][[1]] # Remove from stack stack<-stack[-length(stack)] # Print where we are up to in the stack print(current$val) # Add the node's children to it. # Check if right and left children are present. if(!is.null(current$right$val)){ stack<- append(stack,current$right) } if(!is.null(current$left$val)){ stack<- append(stack,current$left) } } }

Now for running the depth first search:

# Give this a go depthFirstValues(a) ## [1] "a" ## [1] "b" ## [1] "d" ## [1] "e" ## [1] "c" ## [1] "f"

Eureka! We did it!

# Some critiscms

Hadley Wickham wrote in his iconic Advanced R text. “**If you’ve learned OOP in another programming language, it’s likely that R6 will feel very natural […]**”. While I am no expert in OOP, I found the experience of setting up this problem and writing the code quite clunky when contrasted to using a OOP supported language like JavaScript (see Alvin’s JavaScript code in the video and see for yourself) or Python. Besides for `R6Class()`

requiring use of the `=`

operator instead of the `<-`

operator, writing the `initialize`

object in the Node constructor seemed repetitive for this case (but I’m sure it will be useful for others; as far as the `=`

operator there must be some underlying syntax rules preventing the `<-`

operator from being used.).

I was also pretty surprised that I couldn’t find a native `pop()`

function available in base R and as such I needed to manually do it by playing around with the list positions. Finally, I found the indexing looks quite messy. Sure, it works- but I wish it was less messy.

# Conclusion

Despite my critiques about the way the syntax looks, I’m really happy with the end result and the availability of the `R6`

package being pretty straight forward to implement. My critiques likely dome from not having given this package more time before I wrote this and it also could be that there are cleaner solutions to this problem using this package. If you know please tell me!

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