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#

/**
* 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;
};