Leetcode Lowest Common Ancestor of a Binary Search Tree problem solution

YASH PAL,

In this Leetcode Lowest Common Ancestor of a Binary Search Tree problem solution we have given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Leetcode Lowest Common Ancestor of a Binary Search Tree problem solution

Problem solution in Python.

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return
        elif (root.val >= p.val and root.val <= q.val) or (root.val <= p.val and root.val >= q.val):
            return root
        elif root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        else:
             return self.lowestCommonAncestor(root.right,p,q)

Problem solution in Java.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return root;
        if(root.val==p.val || root.val==q.val)
            return root;
        if(root.val>p.val && root.val>q.val)
            return lowestCommonAncestor(root.left,p,q);
        if(root.val<p.val && root.val<q.val)
            return lowestCommonAncestor(root.right,p,q);
        return root;
    }
}

Problem solution in C++.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ll = p;
        TreeNode* hh = q;
        if(p->val > q->val)
        {
            ll=q;
            hh=p;
        }
        while((ll->val!=root->val && hh->val!=root->val) && (ll->val > root->val || root->val > hh->val))
        {
            if(ll->val > root->val)
            {
                root=root->right;
            }
            else if(root->val > hh->val)
            {
                root=root->left;
            }
        }
        return root;
        
    }
};

Problem solution in C.

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q)
{
    struct TreeNode *result = root;

    int v1 = p->val, v2 = q->val;
    p = q = root;
    while (p && q) {
        if (p == q) result = p; else break;
        if (p->val > v1) p = p->left; else if (p->val < v1) p = p->right; else break;
        if (q->val > v2) q = q->left; else if (q->val < v2) q = q->right; else break;
    }
    return result;
}

coding problems