We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Binary Search Tree : Lowest Common Ancestor
  5. Discussions

Binary Search Tree : Lowest Common Ancestor

Sort by

recency

|

765 Discussions

|

  • mdsanz
     + 0 comments

    My Java 8 Solution

    public static Node lca(Node root, int v1, int v2) {
        if (v1 > v2) {
            int temp = v1;
            v1 = v2;
            v2 = temp;
        }
        
      	while (root != null) {
            if (v2 < root.data) {
                root = root.left;
            } else if (v1 > root.data) {
                root = root.right;
            } else {
                return root;
            }
        }
        
        return null;
    }

  • no1isnothing
     + 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!!))

}

  • amitkumar185
     + 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

  • wilson155079
     + 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;
}

  • thomasrussellwo1
     + 0 comments

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