# Lowest Common Ancestor of 2 given nodes in the BST

• We will start traversing from the root node 'r' of the Binary Search Tree(BST).
Let v and w be the nodes we are looking the LCA for.
We assume v and w will be present in the BST.

Note : In a BST, if node n1 is greater than node n , it will be to the right of n and if its smaller than n, it will be to the left of n.
We can use this property and traverse recursively from root to look for LCA of v and w.

If v and w are greater than r, we will traverse recursively to the right.
If v and w are smaller than r, we will traverse recursively to the right.
Else, root is the LCA.

``````# Function to find LCA of v and w.
def lca(root, v, w):

# Base Case
if root is None:
return None

# If both v and w are smaller than root, then LCA lies in left
if(root.data > v and root.data > w):
return lca(root.left, v, w)

# If both v and w are greater than root, then LCA lies in right
if(root.data < v and root.data < w):
return lca(root.right, v, w)

return root
``````

• class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

``````    if(root == null || p == null || q == null)
return null;
if(root == p) return p;
if(root == q) return q;

boolean pIsRigth = checkChildren(root.right, p);
boolean qIsLeft  = checkChildren(root.left, q);

if((pIsRigth && qIsLeft) || (!pIsRigth && !qIsLeft))
return root;
else {

if(pIsRigth && !qIsLeft)
return lowestCommonAncestor(root.right, p, q);
else
return lowestCommonAncestor(root.left, p, q);

}
}

public boolean checkChildren(TreeNode root, TreeNode n) {
if(root == null)
return false;
if(root == n)
return true;
return checkChildren(root.left, n) || checkChildren(root.right, n);
}
``````

}

• ``````    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}

if(root.val == p.val || root.val == q.val) {
return root;
}

if(p.val< root.val && q.val < root.val) {
return lowestCommonAncestor(root.left,p,q);
}

if(p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right,p,q);
}

return root;
}
``````

Time complexity O(log n)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.