[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)