Problem

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

Definition

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.

Note

  • You are given 2 values. Find the lowest common ancestor of the two nodes represented by val1 and val2.
  • No guarantee that val1 and val2 exist in the tree. If one value doesn’t exist in the tree then return -1.
  • There are no duplicate values.
  • You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.

Follow up

What if nodes don’t exist in the tree?

Refer Lowest Common Ancestor of a Binary Tree 2 - Nodes may not exist in Tree.

Solution

Method 1 - Using Post-order Traversal 🏆

We can follow the approach:

  1. Base Cases:
    • If the current node is null, return null.
    • If the current node is one of the nodes (p or q), return the current node.
  2. Recursive Search:
    • Traverse the left subtree to search for p and q.
    • Traverse the right subtree to search for p and q.
  3. Determine LCA:
    • If both left and right subtrees return non-null values, it means p and q are found on both sides, and the current node is their LCA.
    • If only one of the subtrees returns a non-null value, propagate that value upwards.

Code

Java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null || root == p || root == q)  {
	    return root;
	}
	TreeNode left = lowestCommonAncestor(root.left, p, q);
	TreeNode right = lowestCommonAncestor(root.right, p, q);
	
	if (left != null && right != null) {
		return root;
	}
	return left != null ? left : right;
}

Picture for better explanation

Complexity

  • ⏰ Time complexity: O(n), where n is number of nodes in tree, as we traverse the whole tree
  • 🧺 Space complexity: O(h) (assuming recursion tree)

Method 2 - By Storing root to p and q paths using backtracking

Algorithm

  1. Find path from root to p and store it in list.
  2. Find path from root to q and store it in list.
  3. Traverse both paths till the values in arrays are same, and return the common node just before the mismatch.

Code

Java
Node root;
private List<TreeNode> path1 = new ArrayList<>();
private List<TreeNode> path2 = new ArrayList<>();

int lowestCommonAncestor(int p, int q) {
	path1.clear();
	path2.clear();
	return helper(root, p, q);
}

private TreeNode helper(TreeNode root, int p, int q) {

	if (!createPathIfExists(root, p, path1) || !createPathIfExists(root, q, path2)) {
		return null;
	}

	int i;
	for (i = 0; i<path1.size() && i<path2.size(); i++) {
		if (!path1.get(i).equals(path2.get(i))) {
			break;
		}
			
	}

	return path1.get(i - 1);
}

private boolean createPathIfExists(TreeNode root, int child, List<Integer> path) {
	if (root == null) {
		return false;
	}

	path.add(root.val);

	if (root.val == child) {
		return true;
	}

	if (root.left != null && createPathIfExists(root.left, child, path)) {
		return true;
	}

	if (root.right != null && createPathIfExists(root.right, child, path)) {
		return true;
	}

	path.remove(path.size() - 1);

	return false;
}

Complexity

  • ⏰ Time complexity: O(n). The tree is traversed twice, and paths are compared.
  • 🧺 Space complexity: O(n)

Method 3 - Using RMQ

#TODO later.