LeetCode //C - 236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

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 1:

Example 2:

Example 3:

Constraints:

• The number of nodes in the tree is in the range [ 2 , 1 0 5 ] [2, 10^5] [2,105].
• − 1 0 9 < = N o d e . v a l < = 1 0 9 -10^9 <= Node.val <= 10^9 −109<=Node.val<=109
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

From: LeetCode
Link: 236. Lowest Common Ancestor of a Binary Tree

---

Solution:

Ideas：

1. If the current root is NULL, return NULL as we’ve reached the end of a path without finding either p or q.
2. If the current root is either p or q, then the current root is the LCA because by the problem’s definition, a node can be a descendant of itself.
3. Recursively search for p and q in the left and right subtrees of the current root.
4. If both left and right recursive calls return non-NULL values, it means we’ve found p and q in different subtrees of the current root, so the current root is the LCA.
5. If only one of the recursive calls returns a non-NULL value, this means that both p and q are found in one subtree, and the non-NULL node is the LCA.
6. If both left and right are NULL, p and q were not found under this root, so we return NULL.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    // If looking at a null node, return null
    if (root == NULL) return NULL;

    // If either p or q is the root, then the root is the LCA
    if (root == p || root == q) return root;

    // Recursively call the function on the left and right child
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // If both left and right are not null, we found our LCA
    if (left != NULL && right != NULL) return root;

    // If one of the children returned a node, meaning either p or q was found on left or right subtree.
    // If neither was found, then this root can't be LCA
    return left != NULL ? left : right;
}