Skip to Content

Lowest Common Ancestor of a Binary Search Tree

Home | Coding Interviews | Simple Data Structures | Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

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

Posted by Jamie Meyer 25 days ago