Pexels.com

” data-medium-file=”https://bensstats.files.wordpress.com/2021/12/nature-forest-trees-fog.jpeg?w=300″ data-large-file=”https://bensstats.files.wordpress.com/2021/12/nature-forest-trees-fog.jpeg?w=730″ src=”https://bensstats.files.wordpress.com/2021/12/nature-forest-trees-fog.jpeg” alt=”” class=”wp-image-1281″ />

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.