# RObservations #20: Solving “Tree Includes” Problems 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

Following the same style of my previous blogs on binary search. In this blog I present how solve “tree includes” problems in R with R6 objects.

The solutions and the code is based on my translation of Alvin the Programmer’s javascript code into R from his video on binary tree algorithms on FreeCodeCamp’s Youtube channel.

# What is a “Tree Includes” problem?

The term “tree includes” is a term I havent been able to find after googling it. So my explanation (or Alvin’s in his video) of will have to suffice.

Suppose we want to see if a node contains a certain value as one of its children in a (binary) search tree. To check if this is true we can use either a depth-first or breadth-first search to do it.

So for the tree:

a / \ b c / \ \ d e f

If we were to check if `e`

was one of `a`

‘s children, using either a breadth-first or depth-first search will return true. However if we were to start from the node `c`

, using a breadth-first or depth-first starting from there will return false.

# Setting up the problem

As in previous blogs, lets first set up the binary tree.

# 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

For this problem there will be 3 test cases.

- If node
`a`

has contains`e`

(should return true). - If node
`c`

contains`e`

(should return false). - If the
`NULL`

node contains`e`

(should return false).

While it is possible to answer these questions by implementing the breadth-first and depth first search with recursion, I found my experience trying to write the recursive functions in R was fraught with errors and overflow errors. After trying to unsuccessfuly solve it, I decided to opt for using explicitly declarations of the stack and queue instead.

If you have recursive solutions, please let me know!

# Using Breadth-First Search

The function for checking if a tree includes a value as its child is present using breadth first search is:

# Tree Includes # Breadth First # Time: O(n) # Space: O(n) treeIncludesBreadthFirst<-function(root,target){ queue<-c(root) values <- c() while (length(queue)> 0){ current<-queue[[1]] if(current$val==target){ return(TRUE) } values<-append(values,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(FALSE) }

Running it on the test cases, the desired answers are achieved.

treeIncludesBreadthFirst(a,"e") ## [1] TRUE treeIncludesBreadthFirst(c,"e") ## [1] FALSE treeIncludesBreadthFirst(NULL,"e") ## [1] FALSE

# Using Depth-First Search

The function for checking if a tree includes a value as its child is present using depth first search is:

# Tree Includes # Depth First # Time: O(n) # Space: O(n) treeIncludesDepthFirst<-function(root,target){ stack <-c(root) while (length(stack)> 0){ current <- stack[length(stack)][[1]] stack<-stack[-length(stack)] if (current$val==target){return(TRUE)} if(!is.null(current$right$val)){ stack<- append(stack,current$right) } if(!is.null(current$left$val)){ stack<- append(stack,current$left) } } return(FALSE) }

Running it on the test cases, the desired answers are achieved.

treeIncludesDepthFirst(a,'e') ## [1] TRUE treeIncludesBreadthFirst(c,"e") ## [1] FALSE treeIncludesBreadthFirst(NULL,"e") ## [1] FALSE

# Conclusion: Breadth First Search or Depth First Search. Which one is better?

A “tree includes” problem can be solved with either a breadth first search or a depth first search. But which one is better? Well, it depends. A depth first search might be more direct for a shallower tree but may go to unnecessary depth for a deeper tree. A breadth first search may be more helpful for a deeper tree but may travel unnecessary breadth for a wider tree. Context is everything.

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