Leetcode: Lowest Common Ancestor of a Binary Tree

 

This question is asked extremely commonly in big companies such as Facebook, Amazon, Oracle and Microsoft. The problem definition is as follows: 

Given a binary tree, find the lowest common ancestor(LCA) of two given nodes in a tree, which is is the lowest node in a Tree in which have both nodes as its children. Here is the drawing of a tree and 3 examples that follow it: 

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.

Example 3:

Input: root = [1,2], p = 1, q = 2

Output: 1

Now onto the solution, which I am already guessing is a recursive solution. 

Let's think about this real quick.

If the root is p or q, we obviously return the root. We then go on to find the lowest common ancestor in the left tree, and look at the lowest common ancestor in the right subtree to see if we have both these nodes. We return the root if there is no lowest common ancestor of both trees, as this indicates that the left subtree contains one node and the y subtree contains the other node. Otherwise, if left is not null, this means that the left subtree's recursive result is returned. Else, the right recursive subtree is returned. 

public class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        //if one of the nodes is the root, then the common ancestor is obviously the root.

        if(root == null || root == p || root == q) return root;

        //recurse through left and right to get see if there is a common ancestor from both ways

        TreeNode left = lowestCommonAncestor(root.left, p, q);

        TreeNode right = lowestCommonAncestor(root.right, p, q);

        //if neither left or right has both p and q, then the root is the common ancestor

        if(left != null && right != null) return root;

        //if left has a common ancestor, then return that one else return the right. Both can't each have a common ancestor, as that returns to the first base base of returning the root. 

        return left == null ? left : right;

    }

}