Problem

Given values of two nodes in a Binary Tree p and q, find the Lowest Common Ancestor (LCA).

It may be assumed that both nodes exist in the tree and Node has parent pointer.

1
2
3
4
5
6

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

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

Solution

Method 1 - Using Hashtable to create ancestor set

Algorithm

  1. Create an hashset for node p, traversing till root node
  2. Check if q or any of its ancestors exist in hashset, if yes return the first existing ancestor.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// To find LCA of nodes p and q in Binary Tree
public Node lowestCommonAncestor(Node p, Node q) {

	Set<Node> ancestorSet = new HashSet<Node> ();

	// Insert p and all its ancestors in set
	while (p != null) {
		ancestorSet.add(p);
		p = p.parent;
	}

	// Check if q or any of its ancestors exists in set
	while (q != null) {
		if (ancestorSet.contains(q)) {
			return q;
		}
		q = q.parent;
	}

	return null;
}

Complexity

  • ⏰ Time complexity: O(h)
  • 🧺 Space complexity: O(h)

Method 2 - Calculate Height Difference Between 2 Nodes

We may have 2 cases for nodes p and q:

  • Both p and q are at same level ⇨ there is no height difference
  • They are not at same level ⇨ they have height difference

We can solve the problem in O(1) extra space using following fact :

  • Case 1 - Same level - If both nodes are at same level and if we traverse up using parent pointers of both nodes, the first common node in the path to root is LCA.
  • Case 2 - Different level - But if they are at different level, then we move up the deeper node pointer by the depth-difference. Once both nodes reach same level, it becomes like case 1, and we traverse them up and return the first common node.
 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.HashMap;
import java.util.Map;

Node lowestCommonAncestor(Node p, Node q) {
	// Find depths of two nodes and differences
	int d1 = depth(p), d2 = depth(q);
	int diff = d1 - d2;
	// If q is deeper, swap p and q
	// we want p to deeper for traversal
	if (diff < 0) {
		swap(p, q)
		diff = -diff;
	}

	// Move p up until it reaches the same level as q
	while (diff-- != 0) {
		p = p.parent;
	}

	// Now p and q are at same levels
	while (p != null && q != null) {
		if (p == q) {
			return p;
		}

		p = p.parent;
		q = q.parent;
	}

	return null;
}


private int depth(Node node) {
	int d = -1;

	while (node != null) {
		++d;
		node = node.parent;
	}

	return d;
}


private void swap(Node a, Node b) {
	final Node temp = a;
	a = b;
	b = temp;
}

Complexity

  • ⏰ Time complexity: O(h)
  • 🧺 Space complexity: O(1)

Method 3 - Using Y Shaped Linked List Thinking

We have already seen the problem - Y shaped linked list

For eg. Look at LCA of the Trees here:

Now the challenge is height difference. (Similar challenge we had for in Linked list with length difference.).

Code

1
2
3
4
5
6
7
8

public Node lowestCommonAncestor(Node p, Node q) {
	Node a = p, b = q;
	while(a != b) {
		a = a == null ? q: a.parent;
		b = b == null ? p: b.parent;
	}
	return a;
}