Binary Search Tree : Lowest Common Ancestor

Sort by

recency

|

764 Discussions

|

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

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

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

  • + 0 comments

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

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