You are viewing a single comment's thread. Return to all 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")
Seems like cookies are disabled on this browser, please enable them to open this website
Binary Search Tree : Lowest Common Ancestor
You are viewing a single comment's thread. Return to all comments →
The actual LCA function is only 9 lines of R, but stdin/stdout/classes aren't pre-populated.