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:::lcaNode --- 2:::nodeToFind & 8:::nodeToFind
	2 --- 0 & 4
	8 --- 7 & 9
	4 --- 3 & 5

classDef nodeToFind fill:#FF9933,stroke-width:4px;
classDef lcaNode fill:#3399FF,stroke-width:4px;
  
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:::lcaNode & 8
	2 --- 0:::nodeToFind & 4
	8 --- 7 & 9
	4 --- 3 & 5:::nodeToFind

classDef nodeToFind fill:#FF9933,stroke-width:4px;
classDef lcaNode fill:#3399FF,stroke-width:4px;
  
1
2
3

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

Example 3:

graph TD;
	6;
	6 --- 2:::lcaNode & 8
	2 --- 0 & 4:::nodeToFind
	8 --- 7 & 9
	4 --- 3 & 5

classDef nodeToFind fill:#FF9933,stroke-width:4px;
classDef lcaNode fill:#3399FF,stroke-width:4px;
  
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.

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

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - 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

 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
51
52
53
54

public class Solution {
    private TreeNode root;
    private List<TreeNode> path1 = new ArrayList<>();
    private List<TreeNode> path2 = new ArrayList<>();

    public TreeNode 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; // If either p or q is not present.
        }

        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); // Return the lowest common ancestor.
    }

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

        path.add(root);

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

        if (createPathIfExists(root.left, child, path) || createPathIfExists(root.right, child, path)) {
            return true;
        }

        path.remove(path.size() - 1); // Backtrack if child is not found in this path.
        return false;
    }

    public static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int x) {
            val = x;
        }
    }
}
 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

class TreeNode:
    def __init__(self, x: int):
        self.val = x
        self.left: Optional['TreeNode'] = None
        self.right: Optional['TreeNode'] = None

class Solution:
    def __init__(self):
        self.root: Optional[TreeNode] = None
        self.path1: List[TreeNode] = []
        self.path2: List[TreeNode] = []

    def lowestCommonAncestor(self, root: Optional[TreeNode], p: int, q: int) -> Optional[TreeNode]:
        self.path1.clear()
        self.path2.clear()
        if not self.createPathIfExists(root, p, self.path1) or not self.createPathIfExists(root, q, self.path2):
            return None  # If either p or q is not present.

        i = 0
        while i < len(self.path1) and i < len(self.path2):
            if self.path1[i] != self.path2[i]:
                break
            i += 1

        return self.path1[i - 1] if i > 0 else None  # Return the lowest common ancestor.

    def createPathIfExists(self, root: Optional[TreeNode], child: int, path: List[TreeNode]) -> bool:
        if not root:
            return False

        path.append(root)

        if root.val == child:
            return True

        if self.createPathIfExists(root.left, child, path) or self.createPathIfExists(root.right, child, path):
            return True

        path.pop()  # Backtrack if child is not found in this path.
        return False

Complexity

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

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

Picture for better explanation

Code

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

public class Solution {
    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;
    }
}
 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 or root == p or root == q:
            return root

        left: Optional['TreeNode'] = self.lowestCommonAncestor(root.left, p, q)
        right: Optional['TreeNode'] = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left if left else right

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 3 - Using RMQ

#TODO later.