Lowest Common Ancestor

Introduction

 

In this article, we will find the lowest common ancestor node for a given node in a binary tree as well as from a binary search tree. A "common ancestor" for two nodes is a node that has those two nodes as descendants and a node can be a descendant of itself. The "lowest" common ancestor is the node that's closest to the two nodes that satisfies the common ancestor condition.

 

Lowest Common Ancestor In Binary Search Tree

 

Given the root of a binary search tree and two nodes in the tree, left and right, find the lowest common ancestor of p and q. For example, in the following diagram if p is node 2 and q is node 8, then the LowestCommonAncestor(p, q) is node 6. [ Leetcode Question ]

 

 

Here is how we approach to this problem,

1. The current node is p and q is on the left.
2. The current node is p and q is on the right.
3. The current node is q and p is on the left.
4. The current node is q and p is on the right.
5. p is on the left and q is on the right (or vice versa).

We'll take advantage of the search property of binary search trees. In a BST, a node's left children have values that are less than the node's value, and the node's right children have values that are greater than the node's value. Because of this, we'll know if the p is on the left and q is on the right without having to search those subtrees. The C# solution for the problem is given below,

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // iterate through the tree starting from root
        TreeNode current = root;
        while (current == null)
        {
            // either iterate on left(p) or right(q) from the current node
            if (p.val < current.val)
                current = current.left;
            else
                current = current.right;

            // lowest common ancestor found
            if ((p.val <= current.val && q.val >= current.val) ||
               (q.val <= current.val && p.val >= current.val))
                return current;
        }

        // lowest common ancestor not found
        return null;
    }
}

The time complexity of the above algorithm is O(N), or rather, to be specific O(H) where H is the height of the tree. And the space complexity for the same is O(1) because we're not using any extra space, whereas the recursive solution has a space complexity of O(N).

 

Lowest Common Ancestor In Binary Tree

 

Given the root of a binary tree and two nodes in the tree, left and right, find the lowest common ancestor of p and q. For example, in the following diagram if p is node 5 and q is node 1, then the LowestCommonAncestor(p, q) is node 3. [ Leetcode Question ]

 

 

Given below is the algorithm to this problem,

1. The current node is p and q is on the left.
2. The current node is p and q is on the right.
3. The current node is q and p is on the left.
4. The current node is q and p is on the right.
5. p is on the left and q is on the right (or vice versa). 

However, this time we have a regular binary tree, and so we're forced to look through the entire tree until we find p and q. Our strategy is, for each node, recursively check the left and right subtrees to determine if either subtree has p or q in it. The node that satisfies one of these conditions is the lowest common ancestor. Given below is the C# code for the above approach,

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode index = null;
        DoesNodeHasQ(root, p, q, index);
        return index;
    }
    bool DoesNodeHasQ(TreeNode current, TreeNode p, TreeNode q, TreeNode index)  {
        if (current == null)
         return false;

        // does left subtree have p or q
        bool leftSubtreeHasNodeQ = DoesNodeHasQ(current.left, p, q, index);

        // does right subtree have p or q
        bool rightSubtreeHasNodeQ = DoesNodeHasQ(current.right, p, q, index);

        // lowest common ancestor found
        if ((leftSubtreeHasNodeQ && (current == p)) ||
            (leftSubtreeHasNodeQ && (current == q)) ||
            (rightSubtreeHasNodeQ && (current == p)) ||
            (rightSubtreeHasNodeQ && (current == q)) ||
            (leftSubtreeHasNodeQ && rightSubtreeHasNodeQ))
            index = current;

        // return true if the current node is p or q or a descendent of p or q
        return (current == p) ||
            (current == q) ||
            leftSubtreeHasNodeQ ||
            rightSubtreeHasNodeQ;
    }
}

The time complexity for the above algorithm is O(N), because our recursion visits each node exactly once. And the space complexity is O(N) because we potentially hold the entire tree in memory at the same time and moreover the iterative solution requires a stack, hence increasing the space complexity.