Discussion on Binary Search Tree : Lowest Common Ancestor Challenge

Sort by

recency

|

764 Discussions

|

2 months ago+ 0 comments

There's no set up code for doing this in Kotlin, so I wrote some. If you use this, you just need to create 'fun findLowestCommonAncestor(v1: Int, v2: Int, root: Node): Int'

data class Node(
    var left: Node?,
    var right: Node?,
    var data: Int
)

fun placeNode(head: Node, new: Node) {
    // left
    if(head.data > new.data) {
       if(head.left == null) {
           // println("Place Left " + new.data)
            head.left = new
       } else {
            placeNode(head.left!!, new)
       }
    }
    
    // right
    if(head.data < new.data) {
        if(head.right == null) {
            //println("Place Right " + new.data)
            head.right = new
        } else {
            placeNode(head.right!!, new)
        }
    }
}

fun makeBinaryTree(ints: List<Int>): Node? {
    if(ints.size < 1) return null
    
    val root = Node(null, null, ints[0])
    
    for(i in 1..ints.size-1) {
        val node = Node(null, null, ints[i])
        
        placeNode(root, node)
    }
    return root
}

fun main(args: Array<String>) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. */

    val scan = Scanner(System.`in`)

    val nodeCount = scan.nextLine().trim().toInt()
    val item = scan.nextLine()
    val items = item.split(" ").map { it.toInt()}
    //println(items.joinToString())
    val value = scan.nextLine()
    val values = value.split(" ")
    //println(values.joinToString())
    val v1 = values[0].toInt()
    val v2 = values[1].toInt()
    

    val root = makeBinaryTree(items)
    println(findLowestCommonAncestor(v1, v2, root!!))

}

3 months ago+ 0 comments

class Node: def init(self,info): self.info = info
self.left = None
self.right = None

   // this is a node of the tree , which contains info as data, left , right

'''

def lca(root, v1, v2): node=root if node is None: return None if node.info>v1 and node.info>v2: return lca(node.left,v1,v2) elif node.info

3 months ago+ 1 comment

public static Node lca(Node root, int v1, int v2) {
    // Write your code here.        
    if (v1 > root.data && v2 > root.data) {
        // Move to the right subtree
        return lca(root.right, v1, v2);
    }

    if (v1 < root.data && v2 < root.data) {
        // Move to the left subtree
        return lca(root.left, v1, v2);    
    }

    // Found the LCA
    return root;
}

2 months ago+ 0 comments

Ingenious and simple! Because it's a binary search tree, the left side is always be lower than the right side!

4 months ago+ 0 comments

Oddly enough, my solution implemented the same way in Python as in Java failed test cases 2 and 7 only with Python

4 months ago+ 0 comments

    while(r != NULL){
        if(x < r->data && y < r->data)
            r = r->left;
        else if(x > r->data && y > r->data)
            r = r->right;
        else
            break;
    }
    return r;
}

Sort by

|

764 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge