Lowest Common Ancestor of a Binary Tree

Medium

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

Example 1:

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:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

Iterative using parent pointers

Intuition

If we have parent pointers for each node we can traverse back from p and q to get their ancestors. The first common node we get during this traversal would be the LCA node. We can save the parent pointers in a dictionary as we traverse the tree.

Algorithm

  1. Start from the root node and traverse the tree.
  2. Until we find p and q both, keep storing the parent pointers in a dictionary.
  3. Once we have found both p and q, we get all the ancestors for p using the parent dictionary and add to a set called ancestors.
  4. Similarly, we traverse through ancestors for node q. If the ancestor is present in the ancestors set for p, this means this is the first ancestor common between p and q (while traversing upwards) and hence this is the LCA node.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if(root == null){
            return root;
        }
        if(p == null){
            return q;
        }
        if(q == null){
            return p;
        }
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        parentMap.put(root, null);
        populateParentMap(parentMap, root);
        Set<TreeNode> visited = new HashSet<>();
        while(p != null){
            visited.add(p);
            p = parentMap.get(p);
        }
        TreeNode lca = null;
        while(q != null){
            if(visited.contains(q)){
                lca = q;
                break;
            }
            q = parentMap.get(q);
        }
        return lca;
    }
    
    private void populateParentMap(Map<TreeNode, TreeNode> parentMap, TreeNode node){
        if(node == null){
            return;
        }
        TreeNode leftChild = node.left;
        TreeNode rightChild = node.right;
        if(leftChild != null){
            parentMap.put(leftChild, node);
        }
        if(rightChild != null){
            parentMap.put(rightChild, node);
        }
        populateParentMap(parentMap, leftChild);
        populateParentMap(parentMap, rightChild);
    }
}

Complexity Analysis

  • Time Complexity : O(N), where N is the number of nodes in the binary tree. In the worst case we might be visiting all the nodes of the binary tree.
  • Space Complexity : O(N). In the worst case space utilized by the stack, the parent pointer dictionary and the ancestor set, would be N each, since the height of a skewed binary tree could be N.

Categories: Binary Tree

Tagged as: ,

1 reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s