algoadvance

Leetcode 236. Lowest Common Ancestor of a Binary Tree

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Definitions

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

Clarifying Questions

Here are a few clarifying questions to ensure we understand the requirements correctly:

1. Can the nodes p and q be the same?
   • This problem assumes that p and q are distinct nodes in the given tree.
2. Do p and q always exist in the tree?
   • Yes, it is assumed that both nodes exist in the binary tree.
3. Can the binary tree contain duplicate values?
   • Typically for this problem, we assume that all values are unique.

Strategy

1. Recursive Traversal:
   • Perform a depth-first search.
   • Recur for the left subtree and right subtree.
   • If both left and right recursive calls return non-null, it means p and q are found in different branches, hence the current node is the LCA.
   • If one of the recursive calls returns non-null, it means either both p and q are in one subtree, or one is found (we return the non-null result up).
   • If the current node is either p or q, it is an ancestor.
2. Base Cases:
   • If the current node is nullptr, return nullptr.
   • If the current node is equal to p or q, return the current node.

Time Complexity

• Time Complexity: O(N) where (N) is the number of nodes in the binary tree because we potentially visit each node once.
• Space Complexity: O(H) where (H) is the height of the tree due to the recursion stack.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case: if the current node is NULL, return NULL
        if (root == nullptr) {
            return nullptr;
        }
        // If either p or q is the current node, we return the current node
        if (root == p || root == q) {
            return root;
        }

        // Recur for the left and right subtree
        TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);

        // If both the left and right contributions are non-null
        if (leftLCA != nullptr && rightLCA != nullptr) {
            return root;
        }

        // Otherwise check if left subtree or right subtree is the LCA
        return (leftLCA != nullptr) ? leftLCA : rightLCA;
    }
};

This code recursively explores the tree to find the lowest common ancestor by leveraging the depth-first search approach. Each node is evaluated in terms of whether it is the root of the subtree containing both p and q, and the decision is made on that basis.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?