Lowest Common Ancestor LCA in a Binary Tree - Nodes May Not Exist in Tree

Problem

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.

Lowest Common Ancestor Definition

Problems related to it - Lowest Common Ancestor Definition

Examples

Example 1:

1
2
3
4
5
6
7

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
  6       _2_     0        8
         /   \
         7    4

1
2
3

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

Example 2:

1
2
3
4
5
6
7

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
  6       _2_     0        8
         /   \
        7     4

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
Output: null
Explanation: Node 10 does not exist in the tree, so return null.

Follow up

Can you find the LCA traversing the tree, without checking nodes existence?

Solution

Method 1 - Two Pass - Check Nodes Existence

Algorithm

  1. Check if node p and q exists in Tree.
  2. If either of them don’t exist, return null.
  3. Else return the LCA we used to to solve - Lowest Common Ancestor of a Binary Tree#Method 2 - Using Post-order Traversal 🏆.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	boolean l = check(root, p);
	boolean k = check(root, q);
	if(!l || !k) {
		return null;
	}
	return dfs(root, p, q);
}
private boolean check(TreeNode root, TreeNode p) {
	if(root == null) {
		return false;
	}
	
	if(root == p) {
		return true;
	}
	
	return check(root.left, p) || check(root.right, p);
}

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

Method 2 - Recursion with Count of Nodes Found

We can keep track of number of nodes we have found so far. If nodes found is less than 2, then we will return null.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

static class Pair(){
	TreeNode root;
	int count;
	public Pair(TreeNode root, int count) {
		this.root = root;
		this.count = count;
	}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Pair dfsAns = dfs(root, p, q);
    if(dfsAns.count < 2){
	    return null;
    }
    return dfsAns.root;
}

public Pair dfs(TreeNode root, TreeNode p, TreeNode q) {
	if(root == null) {
		return null;
	}
	Pair leftAns = dfs(root.left, p, q);
	Pair rightAns = dfs(root.right, p, q);

	if(root == p || root == q){
		return new Pair(root, 1+leftAns.count + rightAns.count);
	}
	if(leftAns.root != null && leftAns.root != null){
		return new Pair(root, 2);
	}

	return leftAns.root != null? leftAns: rightAns;
}

Method 3 - By Storing root to p and q Paths using backtracking

This approach is same as Lowest Common Ancestor of a Binary Tree#Method 1 - By Storing root to p and q paths using backtracking

Complexity

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