HomeLeetcode236. Lowest Common Ancestor of a Binary Tree - Leetcode Solutions
Leetcode

236. Lowest Common Ancestor of a Binary Tree – Leetcode Solutions

Declan Clarke

Description

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).”

Examples:

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

Solution in Python

Approach:

  1. If the current node is None, return None because we’ve reached the end of a path.
  2. If the current node is equal to p or q, return the current node because one of the targets has been found.
  3. Recursively search for p and q in both the left and right subtrees.
  4. If p and q are found in different subtrees, the current node is their lowest common ancestor.
  5. If both are found in the left or both in the right subtree, the LCA is in that subtree.
Python
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base case: if root is None, or root is either p or q, return root
        if root is None or root == p or root == q:
            return root
        
        # Recursively search for p and q in the left and right subtrees
        left = self.lowestCommonAncestor(root.left, p, q)   # Search in the left subtree
        right = self.lowestCommonAncestor(root.right, p, q) # Search in the right subtree
        
        # If both left and right are non-null, p and q are in different subtrees,
        # so the current root is their lowest common ancestor
        if left and right:
            return root
        
        # If only one side (either left or right) has returned a node,
        # it means both p and q are in that subtree.
        # So return the non-null node (either left or right).
        return left if left else right

Explanation:

  1. Base Case:
    • If the current node (root) is None, that means we’ve reached a leaf node without finding p or q. We return None.
    • If root is either p or q, return root because one of the targets has been found.
  2. Recursive Calls:
    • We search both the left and right subtrees by making recursive calls to lowestCommonAncestor() for root.left and root.right.
  3. Check if Current Node is the LCA:
    • If both recursive calls return non-None values (i.e., both left and right are non-null), it means p was found in one subtree, and q was found in the other. Therefore, the current node (root) is their LCA.
  4. Return Result:
    • If only one of left or right is non-null, it means both p and q are in the same subtree. In this case, return the non-null value (left or right).

Solution in Javascript

JavaScript
var lowestCommonAncestor = function(root, p, q) {
    // Base case: if root is null, or root is either p or q, return root
    if (root === null || root === p || root === q) {
        return root;
    }

    // Recur for the left and right subtrees
    const left = lowestCommonAncestor(root.left, p, q);  // Search in left subtree
    const right = lowestCommonAncestor(root.right, p, q); // Search in right subtree

    // If both left and right are non-null, this means p and q are in different subtrees,
    // so the current node is the lowest common ancestor
    if (left !== null && right !== null) {
        return root;
    }

    // Otherwise, return the non-null value (if either left or right is non-null)
    return left !== null ? left : right;
};

Solution in Java

Java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null, or root is either p or q, return root
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recur for the left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);  // Search in left subtree
        TreeNode right = lowestCommonAncestor(root.right, p, q); // Search in right subtree

        // If both left and right are non-null, p and q are in different subtrees,
        // so the current node is the lowest common ancestor
        if (left != null && right != null) {
            return root;
        }

        // Otherwise, return the non-null value (either left or right)
        return (left != null) ? left : right;
    }
}

Solution in C++

C++
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case: if root is null or root is either p or q, return root
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // Recursively search in the left subtree
        TreeNode* left = lowestCommonAncestor(root->left, p, q);

        // Recursively search in the right subtree
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // If both left and right are non-null, p and q are in different subtrees,
        // so the current root is their lowest common ancestor
        if (left != nullptr && right != nullptr) {
            return root;
        }

        // If only one of left or right is non-null, return that node
        // This means both p and q are in the same subtree
        return left != nullptr ? left : right;
    }
};

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com