Creating Binary Search Tree in R

Question

I have this code for creating a Binary Search Tree in a R6 class.

Creating a Node & BST class. In BST class, I am defining insert_recur function to create the BST by appropriately inserting the data.

library(R6)

Node <- R6Class(  
  classname = 'Node',  
  public = list(
    
    val = NULL,
    left = NULL,
    right = NULL,
    
    initialize = function(val = NULL, left = NULL, right = NULL){
      
      self$val <- val
      self$left <- left
      self$right <- right
      
    }
  )
)

BST <- R6Class(
  
  classname = 'BST',
  
  public = list(
    
    root = NULL,
    # node = NULL,
    
    insert = function(data){
      
      if(is.null(self$root)){
        self$node <- Node$new(data)
      }else{
        self$insert_recur(data, self$root)
      }
      
    },
    
    insert_recur = function(data, cur_node){
      
      if(data < cur_node$val){
        if(is.null(cur_node$self)){
          cur_node$left <- Node$new(data)
        }else{
          insert_recur(data, cur_node$left)
        }
      }else if(data > cur_node$val){
        if(is.null(cur_node$self)){
          cur_node$right <- Node$new(data)
        }else{
          insert_recur(data, cur_node$right)
        }
      }else{
        print('value already in tree')
      }
      
    },
    
    get_height = function(cur_node){
      
      if(is.null(cur_node$val)){
        return(-1)
      }else{
        return(max(self$get_height(cur_node$left),self$get_height(cur_node$right))+1)
      }
    }
    
  )
  
)



bst <- BST$new()
bst$insert(3)
bst$insert(2)
bst$insert(1)
bst$insert(5)
bst$insert(6)
bst$insert(4)
bst$insert(7)

However I am getting this error - Error in self$node <- Node$new(data) : cannot add bindings to a locked environment

If I put node <- NULL in the BST class, then the recursion fails & all nodes are NULL.

What will be the correct implementation?

Allan Cameron · Answer

Your Node implementation is fine. The BST isn't quite right though. It should have a NULL root node only. The problem lies in your insert_recur function. It's not possible for cur_node$self to ever be NULL, and the logic would seem to indicate that your if statements should be checking for the absence of cur_node$left and cur_node$right instead. Also, you need to remember to use self$insert_recur. The logic of your get_height argument doesn't seem right to me either. The following implementation seems to work as expected:

BST <- R6Class(
  
  classname = 'BST',
  
  public = list(
    
    root = NULL,
    
    insert = function(data) {
      
      if(is.null(self$root)) {
        self$root <- Node$new(data)
      } else {
        self$insert_recur(data, self$root)
      }
      
    },
    
    insert_recur = function(data, cur_node) {
      
      if(data < cur_node$val) {
        if(is.null(cur_node$left)) {
          cur_node$left <- Node$new(data)
        } else {
          self$insert_recur(data, cur_node$left)
        }
      } else if(data > cur_node$val){
        if(is.null(cur_node$right)){
          cur_node$right <- Node$new(data)
        }else{
          self$insert_recur(data, cur_node$right)
        }
      }else{
        print('value already in tree')
      }
      
    },
    
    get_height = function(cur_node){
      
      if(is.null(cur_node$left) & is.null(cur_node$right)){
        return(0)
      }else{
        return(max(self$get_height(cur_node$left), 
                   self$get_height(cur_node$right)) + 1)
      }
    }
    
  )
  
)

This allows

bst <- BST$new()
bst$insert(3)
bst$insert(2)
bst$insert(1)
bst$insert(5)
bst$insert(6)
bst$insert(4)
bst$insert(7)

bst$get_height(bst$root)
#> [1] 3
bst$get_height(bst$root$right)
#> [1] 2

^{Created on 2022-09-24 with reprex v2.0.2}

Creating Binary Search Tree in R

1 Answers