Introduction

In my previous blogs, I introduced how to preform depth-first and breadth-first searches in R with R6 objects. After knowing how to do this I explored solving tree-includes problems with both of these searches. In this blog I am going to share how to solve binary “tree sum” problems using recursive and iterative approaches. As was the case with previous blogs, this blog was written based on Alvin the Programmer’s video on binary tree algorithms for technical interviews, but specified for the R user.

The Problem

The problem of finding a binary tree sum relates to finding the sum of all the nodes in a given tree. For the tree:

          3
         / \
        11  4
       /  \  \
      4    2  1

It is possible to find the sum (25) using with either recursive or iterative approaches.

To set up the above tree we will use R6 classes. If you have read the previous blogs, the objects are the same but are specified for this problem.

The R code for doing this is:

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
                  }
                )
                )


a<-node$new(val=3)
b <- node$new(val=11)
c<-node$new(val=4)
d <- node$new(val=4)
e<-node$new(val=2)
f <- node$new(val=1)

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

Using Recursion.

In my last blog, I shared how I was unable to write a depth-first solution in R with recursion. However this time, I was able to figure it out thanks to this answer on StackOverflow. Apparently, for recursion R will not allow for “vector notation” to be implemented, as such list notation should be used. In other words, for recursion, avoid using $ to index variables as your code will result in an error. Instead use [[]].

The recursive tree-sum code is:

treeSum <- function(root){

  # Dealing with null values
  if(is.null(root[['val']])){
    return(0)
  }

  # The magic of recursion
  return(root[['val']] + treeSum(root[['left']])+ treeSum(root[['right']]))

}

treeSum(a)


## [1] 25

Using an iterative approach

To solve this problem iteratively, all that needs to be done is to modify the breadth first code to calculate a rolling sum as the binary tree is traversed. While it is possible to also have an iterative depth first search, because it was already done recursively, breadth first is implemented for this iterative approach.

treeSum <- function(root){
  queue<-c(root)
  totalSum <- 0
  while (length(queue)> 0){
    current<-queue[[1]]

    totalSum <- totalSum + current$val
    if(!is.null(current$left$val)){
      queue<- append(queue,current$left)
    }
    if(!is.null(current$right$val)){
      queue<- append(queue,current$right)
    }
    # remove first element
    queue<-queue[-1]
  }
  return(totalSum)

}

treeSum(a)


## [1] 25

Conclusion

There you have it! Another binary tree problem in the books! I’m pretty happy I got to figure out how recursion works and how to implement it in R. It definitely makes for cleaner looking code. I hope to be able to use it for future projects and make cleaner R code with it and R6 objects!