Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    The actual LCA function is only 9 lines of R, but stdin/stdout/classes aren't pre-populated.

    library(magrittr)
    
    Node <- setRefClass(
      "Node",
      fields = list(
        info = "numeric",
        left = "ANY",
        right = "ANY"
      ),
      methods = list(
        initialize = function(info) {
          .self$info <- info
          .self$left <- NULL
          .self$right <- NULL
        },
        toString = function() {
          as.character(.self$info)
        }
      )
    )
    
    BinarySearchTree <- setRefClass(
      "BinarySearchTree",
      fields = list(
        root = "ANY"
      ),
      methods = list(
        initialize = function() {
          .self$root <- NULL
        },
        create = function(val) {
          newNode <- Node$new(info = val)
          if (is.null(.self$root)) {
            .self$root <- newNode
          } else {
            current <- .self$root
            repeat {
              if (val < current$info) {
                if (!is.null(current$left)) {
                  current <- current$left
                } else {
                  current$left <- newNode
                  break
                }
              } else if (val > current$info) {
                if (!is.null(current$right)) {
                  current <- current$right
                } else {
                  current$right <- newNode
                  break
                }
              } else {
                break
              }
            }
          }
        }
      )
    )
    
    lca <- function(root, v1, v2) {
      if (root$info < v1 && root$info < v2) {
        lca(root$right, v1, v2)
      } else if (root$info > v1 && root$info > v2) {
        lca(root$left, v1, v2)
      } else {
        root
      }
    }
    
    stdin <- file('stdin', 'r')
    inp <- readLines(stdin, n = 3, warn = FALSE)
    close(stdin)
    
    n <- as.integer(inp[1])
    treeInput <- strsplit(inp[2], " ") %>% unlist %>% as.integer
    vertexes <- strsplit(inp[3], " ") %>% unlist %>% as.integer
    bst <- BinarySearchTree$new()
    for (n in treeInput) {
      bst$create(n)
    }
    ans <- lca(bst$root, vertexes[1], vertexes[2])
    cat(ans$info, "\n")