Binary Search Tree : Lowest Common Ancestor

Sort by

recency

|

763 Discussions

|

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

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

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

    Solution with commented explanation.

    public static Node lca(Node root, int v1, int v2) { // Write your code here. return recLca(root, v1, v2); } public static Node recLca(Node root, int v1, int v2) { if (root == null) { return null; } if (root.data == v1 || root.data == v2) { return root; } Node leftFind = recLca(root.left, v1, v2); Node rightFind = recLca(root.right, v1, v2); if (leftFind == null || rightFind == null) { return leftFind == null ? rightFind : leftFind; } if (leftFind.data == rightFind.data) { return leftFind; } else{ return root; } }