LeetCode: 236. Lowest Common Ancestor of a Binary Tree

The 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.

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if ( root == NULL ) return NULL;

    if (root->val == p->val || root->val == q->val) return root;

    TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
    TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);

    if (leftLCA != NULL && rightLCA != NULL) return root;

    return leftLCA != NULL ? leftLCA : rightLCA;
}

Let's break down the code in a simple way:

This code finds the lowest common ancestor (LCA) of two nodes in a binary tree.

• It starts at the root of the tree.
• If the root is empty (NULL), it means there's nothing to search, so it returns nothing (NULL).
• If the root's value is equal to either of the two nodes (p or q), it means one of them is found at this point, so it returns the root as a candidate for the LCA.
• It then looks for the LCA in the left and right subtrees of the current node by calling itself recursively.
• If both the left and right subtrees found valid candidates for LCA (not NULL), it means the current node is the lowest common ancestor, so it returns the current node.
• If only one subtree found a valid LCA candidate, it returns that candidate. If both subtrees found nothing, it returns NULL.