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
  
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
  
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:

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.

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

Java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	if (root == null || p == null || q == 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;
	}
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

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:

// 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:

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

Code

Java
public Node LCA (Node root, Node p, Node q) {
	while (root != null) {
		// If root>p and root>q then lowest common ancestor will be in left subtree
		if (root.val > p.val && root.val > q.val) {
			root = root.left;
		}
		// If root<p and root<q then lowest common ancestor will be in right subtree
		else if (root.val<= p.val && root.val<q.val) {
			root = root.right;
		}
		// if I am here that means i am at the root which is lowest common ancestor
		else {
			return root;
		}
	}
	return root;
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)