RObservations #20: Solving “Tree Includes” Problems for Binary Trees

[This article was first published on 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.

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″ />
Photo by Jaymantri on Pexels.com

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!

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

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)