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!

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

```# Tree Includes
# Time: O(n)
# Space: O(n)

queue<-c(root)
values <- c()
while (length(queue)> 0){
current<-queue[]

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

##  TRUE

##  FALSE

##  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)][]
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')

##  TRUE

##  FALSE

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