RObservations #21: Solving “Tree Sum” Problems with Recursion and Iterative Approaches
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
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!
Want to see more of my content?
Be sure to subscribe and never miss an update!
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.