[algorithm] How to find the lowest common ancestor of two nodes in any binary tree?

Solution 1: Recursive - Faster

  • The idea is to traverse the tree starting from root. If any of the given keys p and q matches with root, then root is LCA, assuming that both keys are present. If root doesn’t match with any of the keys, we recurse for left and right subtree.
  • The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.
  • Time Complexity: O(n)
  • Space Complexity: O(h) - for recursive call stack
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)
            return right;
        else if(right == null)
            return left;
        else
            return root;    // If(left != null && right != null)
    }
}

Solution 2: Iterative - Using parent pointers - Slower

  • Create an empty hash table.
  • Insert p and all of its ancestors in hash table.
  • Check if q or any of its ancestors exist in hash table, if yes then return the first existing ancestor.
  • Time Complexity: O(n) - In the worst case we might be visiting all the nodes of binary tree.
  • Space Complexity: O(n) - Space utilized the parent pointer Hash-table, ancestor_set and queue, would be O(n) each.
class Solution
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
        HashSet<TreeNode> ancestors_set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();

        parent_map.put(root, null);
        queue.add(root);

        while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
        {
            TreeNode node = queue.poll();

            if(node.left != null)
            {
                parent_map.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null)
            {
                parent_map.put(node.right, node);
                queue.add(node.right);
            }
        }

        while(p != null)
        {
            ancestors_set.add(p);
            p = parent_map.get(p);
        }

        while(!ancestors_set.contains(q))
            q = parent_map.get(q);

        return q;
    }
}

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to binary-tree

Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Difference between binary tree and binary search tree Heap vs Binary Search Tree (BST) C linked list inserting node at the end How to print binary tree diagram? With ' N ' no of nodes, how many different Binary and Binary Search Trees possible? How to implement a binary tree? Find kth smallest element in a binary search tree in Optimum way What are the applications of binary trees? How to find the lowest common ancestor of two nodes in any binary tree?

Examples related to complexity-theory

Differences between time complexity and space complexity? Determining complexity for recursive functions (Big O notation) How to find time complexity of an algorithm How can building a heap be O(n) time complexity? HashMap get/put complexity Big-oh vs big-theta Is log(n!) = T(n·log(n))? Time complexity of accessing a Python dict What are the differences between NP, NP-Complete and NP-Hard? What's the fastest algorithm for sorting a linked list?

Examples related to least-common-ancestor

How to find the lowest common ancestor of two nodes in any binary tree?