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

|

768 Discussions

|

  • suxihong07
     + 0 comments

    python code:

    def lca(root, v1, v2):

    if root.info > v1 and root.info > v2:

       return  lca(root.left,v1,v2)

    elif root.info < v1 and root.info < v2:

       return lca(root.right,v1,v2)

    else: return root

  • safee7
     + 0 comments

    C++ `14 Solution:

             
//O(h) - h is height of the binary search tree ----> O(log(n))
//Worst case (Skewed BST): Height h = n -- O(n). 
    Node *lca(Node *root, int v1,int v2) {
        if(root == nullptr) return root;
        while(root){
            if(v1 < root->data && v2 < root->data)
                root= root->left;
            else if(v1 > root->data && v2 > root->data)
                root = root->right;
            else
                return root;
        }
        return root;
    }

  • onlypathan
     + 0 comments

    How frist image can be a BST? The left child (4) is greater than its parent node (3), which violates the Binary Search Tree property. Do I missing something?

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

}