Binary Search Tree : Lowest Common Ancestor

Sort by

recency

|

34 Discussions

|

  • + 0 comments
    def get_chain(root, val, chain):
        if not root:
            return None
        if root.info == val:
            chain = chain + (root,)
            return chain
        left_result = get_chain(root.left, val, chain)
        if left_result:
            return left_result + (root,)
        right_result = get_chain(root.right, val, chain)
        if right_result:
            return right_result + (root,)
        return chain
    
    
    def lca(root, v1, v2):
        x = get_chain(root, v1, ())
        y = get_chain(root, v2, ())
        x = list(x)
        y = set(y)
        common = None
        for i in range(len(x)):
            if x[-(i+1)] in y:
                common = x[-(i+1)]
        return common
    
  • + 0 comments

    Here is Hackerrank binary search tree lowest common ancestor problem solution in python java c++ c and javascript

  • + 0 comments

    The first example given is NOT a binary search tree. HackerRank, please fix it. It is confusing.

  • + 1 comment
    from collections import deque
    
    def lca(root, v1, v2):
        if root is None: 
            return None
        
        # Find path from root to target node
        def findPathToTarget(root, target_int):
            dq = deque([(root, [])])
            while dq:
                node, path = dq.popleft()
                new_path = path + [node]  # Create a new path list
                if node.info == target_int:
                    return new_path
                if node.left:
                    dq.append((node.left, new_path))
                if node.right:
                    dq.append((node.right, new_path))
            return []
    
        # Get paths to v1 and v2
        path_to_v1 = findPathToTarget(root, v1)
        path_to_v2 = findPathToTarget(root, v2)
    
        # Compare paths to find LCA
        lca = None
        for a, b in zip(path_to_v1, path_to_v2):
            if a == b:
                lca = a
            else:
                break
        return lca
    
  • + 0 comments

    C#:

    public Node LowestCommonAncestor(Node n1, Node n2)
    {
        if (n1.FindNode(n2.Data) != null) return n1;
        if (n2.FindNode(n1.Data) != null) return n2;
        if(n1.Parent ==  n2.Parent) return n1.Parent;
        return LowestCommonAncestor(n1.Parent, n2.Parent);
    }