Problem

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

Definiton

Lowest Common Ancestor Definition

Problems related to it - Lowest Common Ancestor Definition

Examples

Example 1:

graph TD;
	6;
	6 --- 2;
	6 --- 8;
	2 --- 0;
	2 --- 4;
	8 --- 7;
	8 --- 9;
	4 --- 3;
	4 --- 5;

style 2 fill:#FF9933
style 8 fill:#FF9933
style 6 fill:#3399FF
  
1
2
3

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

graph TD;
	6;
	6 --- 2;
	6 --- 8;
	2 --- 0;
	2 --- 4;
	8 --- 7;
	8 --- 9;
	4 --- 3;
	4 --- 5;

style 2 fill:#FF9933
style 4 fill:#FF9933
style 2 fill:#3399FF
  
1
2
3

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

1
2

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints

  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

Solution

Here we will focus on BST.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Recursion or Iteration and Key Comparison

  1. Start will the root.
  2. If root > p and root > q then LCA will be in left subtree.
  3. If root < p and root < q then LCA will be in right subtree.
  4. If Step 2 and Step 3 is false then we are at the root which is lowest common ancestor, return it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) {
			return null;
		}
		if (root.val > p.val && root.val > q.val) {
			return lowestCommonAncestor(root.left, p, q);
		} else if (root.val < p.val && root.val < q.val) {
			return lowestCommonAncestor(root.right, p, q);
		} else {
			return root;
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def lowestCommonAncestor(self, root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
        if not root:
            return None

        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q) # Both p and q are in the left subtree

        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q) # Both p and q are in the right subtree

        return root # We have found the split point, i.e., the LCA node.

Complexity

  • ⏰ Time complexity: O(log n) if the tree is balanced; O(n) if the tree is skewed.
  • 🧺 Space complexity: O(h) where h is the height of the tree (which can be O(n) in the worst case).

What if it is Not Guaranteed That P and Q Will Be in Tree?

Then we can add isNodePresent function and call it before calling our LCA function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Function to check if a given node is present in a binary tree or not
public static boolean isNodePresent(Node root, Node node) {
	// base case
	if (root == null) {
		return false;
	}

	// if the node is found, return true
	if (root == node) {
		return true;
	}

	// return true if a given node is found in the left or right subtree
	return isNodePresent(root.left, node) || isNodePresent(root.right, node);
}

Driver code:

1
2
3
4
5
6

boolean pPresent = isNodePresent(root, p);
if (!pPresent) return null;
boolean qPresent = isNodePresent(root, q);
if (!qPresent) return null;

return lowestCommonAncestor(root, p, q);

Method 2 - Iterative

Here is the approach:

  • Start from the root node:
    • If both p and q are smaller than the root, then LCA lies in the left subtree.
    • If both p and q are greater than the root, then LCA lies in the right subtree.
    • If one of p or q is smaller than the root and the other is greater, then the root is the LCA.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left; // Both p and q are in the left subtree
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right; // Both p and q are in the right subtree
            } else {
                // We have found the split point, i.e., the LCA node.
                return root;
            }
        }
        return null; // Only if root is null (shouldn't happen in valid BST)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def lowestCommonAncestor(self, root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left # Both p and q are in the left subtree
            elif p.val > root.val and q.val > root.val:
                root = root.right # Both p and q are in the right subtree
            else:
                return root # We have found the split point, i.e., the LCA node.
        return None # Only if root is null (shouldn't happen in valid BST)

Complexity

  • ⏰ Time complexity: O(log n) if the tree is balanced; O(n) if the tree is skewed.
  • 🧺 Space complexity: O(1)