Tuesday, October 4, 2011

[Amazon] Find Least Common Ancestor of two nodes in a Binary Tree

Problem: 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:

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.
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.
Input: root = [1,2], p = 1, q = 2
Output: 1


Approach: Its an straight forward solution which can be understood by just looking at the code. Please note that we are using Post order traversal approach here.


Implementation in C#:

       public TreeNode LowestCommonAncestor(TreeNode root,
                                         TreeNode p,
                                         TreeNode q)
    {
        if (root == null)
        {
            return null;
        }

        if (root == p || root == q)
        {
            return root;
        }

        TreeNode leftLCA = this.LowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = this.LowestCommonAncestor(root.right, p, q);
        if (leftLCA != null && rightLCA != null)
        {
            return root;
        }
        else if (leftLCA != null)
        {
            return leftLCA;
        }
        else if (rightLCA != null)
        {
            return rightLCA;
        }
        return null;
    }


Complexity: O(n)

No comments:

Post a Comment