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!