Lowest Common Ancestor of a Binary Search Tree - Depth First Search / Binary Search Tree

Problems
1

https://algo.monster/problems/lowest_common_ancestor_on_bst

2

A simpler one:


def lca_on_bst(bst: Node, p: int, q: int) -> int:
    def lca_subtree(node):
        if p1 <= node.val <= q1:
            return node
        if p1 <= node.val and q1 <= node.val:
            return lca_subtree(node.left)
        else:
            return lca_subtree(node.right)
            
    p1, q1 = min(p, q), max(p, q)
    return lca_subtree(bst).val
3 
public static int lcaOnBst(Node<Integer> bst, int p, int q) {
        // WRITE YOUR BRILLIANT CODE HERE
        if((p > (int)bst.val && q < (int)bst.val) || (p < (int)bst.val && q > (int)bst.val)) 
            return bst.val;
        else if(p < (int)bst.val && q < (int)bst.val) 
            return lcaOnBst(bst.left,p,q);
        else if(p > (int)bst.val && q > (int)bst.val) 
            return lcaOnBst(bst.right , p, q);
        else if((int)bst.val == p || (int)bst.val == q) 
            return bst.val;
        return -1;
    }
4

def lca_on_bst(bst: Node, p: int, q: int) → int:
# WRITE YOUR BRILLIANT CODE HERE
if not bst: return
if p == bst.val or q == bst.val:
return bst.val
elif p < bst.val and q < bst.val:
return lca_on_bst(bst.left, p, q)
elif p > bst.val and q > bst.val:
return lca_on_bst(bst.right, p, q)
return bst.val

5 

def lca_on_bst(bst: Node, p: int, q: int) -> int:
    # WRITE YOUR BRILLIANT CODE HERE
    if not bst: return
    if p == bst.val or q == bst.val:
        return bst.val
    elif p < bst.val and q < bst.val:
        return lca_on_bst(bst.left, p, q)
    elif p > bst.val and q > bst.val:
        return lca_on_bst(bst.right, p, q)
    return bst.val
6

A simpler solution:
`def lca_on_bst(bst: Node, p: int, q: int) → int:

lca = bst.val

if p < lca and q < lca:
    return lca_on_bst(bst.left, p, q)

if p > lca and q > lca:
    return lca_on_bst(bst.right, p, q)

return lca`
7

If nodes p and q are on the right of the current node, then the root node of the BST will be the lowest common ancestor (because all nodes to the right of the root node are larger than the root node value. No?

8

the above at least applies to the corner case where both p & q are larger than the root node.

9

It seems lowest is in terms of depth, and not in terms of value - so lowest is the deepest!

10

A more simple approach:

def lca_on_bst(bst: Node, p: int, q: int) → int:

p can be LCA

q can be LCA

parent of p and q can be LCA given that p and q are on diff sides

if not bst:
    return None

if (p <= bst.val <= q) or (q <= bst.val <= p):
    return bst.val
elif p < bst.val:
    return lca_on_bst(bst.left, p, q)
else:
    return lca_on_bst(bst.right, p, q)
11

Another solution
def lca_on_bst(bst: Node, p: int, q: int) → int:
while(True):
if bst.val > p and bst.val > q:
bst = bst.left
elif bst.val < p and bst.val < q:
bst = bst.right
else:
return bst.val

12

def lca_on_bst(bst: Node, p: int, q: int) → int:
while(True):
if bst.val > p and bst.val > q:
bst = bst.left
elif bst.val < p and bst.val < q:
bst = bst.right
else:
return bst.val

13

Structured Programming JS Solution:

function lcaOnBst(bst, p, q) {
    let result = bst.val;
    
    if (p != result && q != result) {
        if (p < result && q < result) {
            result = lcaOnBst(bst.left, p, q);
        } else if (p > result && q > result) {
            result = lcaOnBst(bst.right, p, q);
        }
    }

    return result;
}
14

def lca_on_bst(bst: Node, p: int, q: int) → int:
# WRITE YOUR BRILLIANT CODE HERE
def dfs(root):
if not root: return
if root.val == p or root.val == q: # if cur val equals p or q then it is the LCA
return root.val
if root.val < p and root.val < q: # search right
return dfs(root.right)
elif root.val > p and root.val > q: # search left
return dfs(root.left)
else:
return root.val # in_between
return dfs(bst)

15

I think this is easier to read

public static int lcaOnBst(TreeNode<Integer> bst, int p, int q) {
    // WRITE YOUR BRILLIANT CODE HERE
    if(p == q) return p;
    return findAncestor(bst, Math.min(p, q), Math.max(p,q));
}

public static int findAncestor(TreeNode<Integer> node, int smallerChild, int largerChild) throws IllegalArgumentException {
    if(node == null) throw new IllegalArgumentException("child nodes do not exist in tree"); // this shouldn't happen
    if(node.val >= smallerChild && node.val <= largerChild) return node.val;
    else if (node.val > smallerChild && node.val > largerChild) return findAncestor(node.left, smallerChild, largerChild);
    else return findAncestor(node.right, smallerChild, largerChild);
}
16

I used below approach:

def lca_on_bst(bst: Node, p: int, q: int) → int:
if not bst:
return 0

left, right = (p , q) if p <= q else (q, p)

if bst.val < left:
    return lca_on_bst(bst.right, p, q)
elif bst.val > right:
    return lca_on_bst(bst.left, p, q)
else:
    return bst.val
17

The Python code can definitely be simplified!

def lca_on_bst(bst: Node, p: int, q: int) -> int:
    if p < bst.val and q < bst.val:
        return lca_on_bst(bst.left, p, q)
    elif p > bst.val and q > bst.val:
        return lca_on_bst(bst.right, p, q)
    else:
        return bst.val
18

:+1:

19

What a wonderfully explained solution!

20

It may be worth it to note that the given p and q are guaranteed to be in the tree.

I spent way too long trying to figure out an algorithm where p or q might not actually be in the tree and returning a no-ancestor shared case. But hey, good practice right? :sweat_smile:

1 Like