LC236. Lowest Common Ancestor of a Binary Tree

Problem Description

Source: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Given a binary tree, return 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).”

For example: Given binary tree [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], where p = 5, and q = 1,

        3
      /   \
     5     1
    / \   / \
   6  2  0   8
     / \
    7   4

return 3.

Solution

High level strategy

Our approach to this problem is to solve it recursively. In our base case, we return the current node if it is equal to 'p', 'q', or null. This way, we will receive falsy values as we recurse down a branch that does not contain either 'p' or 'q'. Therefore, if either the left or right side of the current node returns null, then we know that that side of the tree does not contain the target values, and we can simply check the opposite side. We repeat this process until we arrive at a subtree that contains both target values, at which point we return the root node of the subtree. The time complexity of this solution is O(n), where 'n' is equal to the number of nodes. The space complexity is O(logn), or O(h), where 'h' is equal to the height of the tree.

Code

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 **/
const lowestCommonAncestor = (root, p, q) => {
    if (root === null || root === p || root === q) return root;
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q); 
    
    if (!left) return right;
    if (!right) return left;
    
    return root;
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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);
    return left == null ? right : right == null ? left : root;
}

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """

        if not root:
            return root 

        if root == p or root == q: 
            return root 

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        else:
            return left or right