Posts Lowest Common Ancestor of a Binary Tree
Post
Cancel

Lowest Common Ancestor of a Binary Tree

PROBLEM DESCRIPTION

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

leetcode

SOLUTION (NOT OPTIMAL)

1
2
3
4
5
6
7
       ____3____
      /         \
   __5__        _1__
  /     \      /    \
 6       2    0      8
        / \
       7   4

Inorder traversal of the tree is: 6 5 7 2 4 3 0 1 8

Given:
p = 5 and q = 1

3 is the root element in this case. We notice that index of p is less than that, and index of q is more. That means, p and q must be lying of different side of the current node and it can be marked as LCA.

If both p and q were on left side of current root, we can update root to root.left.
If both p and q were on right side of current root, we can update root to root.right.

If can happen can current root is equal to either p or q. (For example, if p is a child of q). In that case, the current root, which would be equal to either p or q can be marked as LCA. We can use this condition in a while loop.

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
class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Perform an in-order traversal of the tree to get the list of nodes in in-order sequence
        List<TreeNode> inorder = inorder(root, new ArrayList<>());

        TreeNode current = root; // Start traversal from the root node

        int pIndex = getIndex(inorder, p); // Get the index of node p in the in-order list
        int qIndex = getIndex(inorder, q); // Get the index of node q in the in-order list

        int rootIndex = getIndex(inorder, current); // Get the index of the current root in the in-order list

        // Traverse the tree until the root node's index matches either p's index or q's index
        while (rootIndex != pIndex && rootIndex != qIndex) {
            if (pIndex < rootIndex && qIndex < rootIndex) {
                current = current.left; // Move to the left child if both p and q are in the left subtree
                rootIndex = getIndex(inorder, current); // Update the current root's index
            } else if (pIndex > rootIndex && qIndex > rootIndex) {
                current = current.right; // Move to the right child if both p and q are in the right subtree
                rootIndex = getIndex(inorder, current); // Update the current root's index
            } else {
                return current; // If p and q are on different subtrees, the current node is the LCA
            }
        }

        return current; // Return the lowest common ancestor
    }

    // Get the index of a node in the in-order list
    public int getIndex(List<TreeNode> inorder, TreeNode current) {
        for (int i = 0; i < inorder.size(); i++) {
            if (inorder.get(i) == current) return i; // Return the index when the node is found
        }
        return -1; // Return -1 if the node is not found
    }

    // Perform an in-order traversal of the tree and populate the in-order list
    public List<TreeNode> inorder(TreeNode root, List<TreeNode> list) {
        if (root == null) return list; // Base case: Return the list when the node is null

        inorder(root.left, list); // Traverse left subtree
        list.add(root); // Add the current node to the list
        inorder(root.right, list); // Traverse right subtree

        return list;
    }
}

For more optimal solutions, check this out:

This post is licensed under CC BY 4.0 by the author.