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

  • wanyunze
     + 0 comments

    not optimal but still O(h), I simply brute forced and found both the parents and searched the common one.

    let's be honest, are you really able to analyse the three cases and produce the optimal code on the spot? We are software engineers not mathematicians. For me this is like we can memorise and use (phi^n - (1-phi)^n)/sqrt(5) to find fib(n), but we would rather use dynamic programming to bruteforce!

    def lca(root, v1, v2):
    def get_parents(head, x, parents):
        parents.append(head)
        
        if head.info == x:
            return
        if x > head.info:
            get_parents(head.right, x, parents)
        elif x < head.info:
            get_parents(head.left, x, parents)
    
    v1p, v2p = [], []
    get_parents(root, v1, v1p)
    get_parents(root, v2, v2p)
    
    v1p = set(v1p)
    for i in range(len(v2p)-1, -1, -1):
        if v2p[i] in v1p:
            return v2p[i]