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

  • h22028162
     + 0 comments

    C++ Sol: I'm not sure if the given problem has all the properties of BST

    1. with rules: left-descendant node < node < right-descendant node
    Node *lca(Node *root, int v1,int v2) {
        if(v1 < root->data && v2 < root->data){
            return lca(root->left, v1, v2);
        }
        else if(v1 > root->data && v2 > root->data){
            return lca(root->right, v1, v2);
        }
        return root;
    }
    1. no rule, just TREE
    //check if root goes through vertex v
	bool passBy(Node* root, int v){
        if(root == nullptr) return false;
        if(root->data == v) return true;
        return passBy(root->left, v) | passBy(root->right, v);
    }
		
    Node *lca(Node *root, int v1,int v2) {
        if(passBy(root->left, v1) && passBy(root->left, v2))
            return lca(root->left, v1, v2);
        else if(passBy(root->right, v1) && passBy(root->right, v2))
            return lca(root->right, v1, v2);
        else return root;
    }