Solution For Lowest Common Ancestor Of A Binary Search Tree

The problem is to find the lowest common ancestor (LCA) of two nodes in a binary search tree (BST).

A BST is a tree where the left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key.

The solution to this problem involves traversing the BST from the root node until we find a node that lies between the two nodes whose LCA we are trying to find. This node will be the LCA.

Algorithm:

1. Start at the root node of the BST.
2. If the values of both nodes are less than the current node’s value, move to the left subtree.
3. If the values of both nodes are greater than the current node’s value, move to the right subtree.
4. If one of the nodes has the same value as the current node, that node is the LCA.
5. If both nodes have values that are less than or greater than the current node’s value, the current node is the LCA.
6. If the values of the two nodes lie on either side of the current node’s value, move down the tree recursively until the LCA is found.

Code:

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return NULL;
if(p->val > root->val && q->val > root->val) {
return lowestCommonAncestor(root->right, p, q);
} else if(p->val < root->val && q->val < root->val) {
return lowestCommonAncestor(root->left, p, q);
} else {
return root;
}
}
};

In this code, we first check if both nodes are greater than or less than the current node’s value. If they are, we move to the right or left subtree, respectively. If both nodes have values that are less than or greater than the current node’s value, the current node is the LCA. If the values of the two nodes lie on either side of the current node’s value, we move down the tree recursively until the LCA is found.

Step by Step Implementation For Lowest Common Ancestor Of A Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // if the root is null, return null
        if (root == null) {
            return null;
        }
        // if p and q are both smaller than the root, then the LCA must be in the left subtree
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        // if p and q are both larger than the root, then the LCA must be in the right subtree
        } else if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        // otherwise, the root is the LCA
        } else {
            return root;
        }
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # if root is None, return None
        if not root:
            return None
        # if either p or q is the root, return root
        if root == p or root == q:
            return root
        # search the left subtree
        left = self.lowestCommonAncestor(root.left, p, q)
        # search the right subtree
        right = self.lowestCommonAncestor(root.right, p, q)
        # if both left and right are not None, then root is the LCA
        if left and right:
            return root
        # if left is not None, then left is the LCA
        if left:
            return left
        # if right is not None, then right is the LCA
        if right:
            return right

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // if the root is null, we return null
    if (!root) {
        return null;
    }
    
    // if the root's value is greater than p and q, 
    // we know that we need to search the left subtree
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    
    // if the root's value is less than p and q, 
    // we know that we need to search the right subtree
    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    
    // if the root's value is greater than or equal to p's value 
    // and less than or equal to q's value, we know that this is the lowest common ancestor
    return root;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case
        if (root == NULL || root == p || root == q) return root;
        
        // Search in left and right subtrees
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        // If both left and right subtrees have a node that is common to p and q,
        // then the current root is the LCA. Otherwise, the LCA is in the 
        // subtree that contains a common node (if only one of the subtrees 
        // contains a common node, the root of that subtree is the LCA).
        if (left != NULL && right != NULL) {
            return root;
        }
        if (left != NULL) {
            return left;
        }
        if (right != NULL) {
            return right;
        }
        return NULL;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //If the root is null, return null
        if(root == null)
        {
            return null;
        }
        
        //If either p or q is the root, return the root
        if(root == p || root == q)
        {
            return root;
        }
        
        //Check if p and q are on different sides of the root
        //If they are, the root is the LCA
        if((root.val > p.val && root.val < q.val) || (root.val < p.val && root.val > q.val))
        {
            return root;
        }
        
        //If p and q are both less than the root, recurse on the left subtree
        if(p.val < root.val && q.val < root.val)
        {
            return LowestCommonAncestor(root.left, p, q);
        }
        
        //If p and q are both greater than the root, recurse on the right subtree
        if(p.val > root.val && q.val > root.val)
        {
            return LowestCommonAncestor(root.right, p, q);
        }
        
        //If we reach this point, something has gone wrong
        return null;
    }
}