236. Lowest Common Ancestor of a Binary Tree

Hint

/**
 * 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) {
        // If the current node is null, or if it is either p or q, return the current node

        // Recur for the left subtree
        // Recur for the right subtree

        // If both left and right are non-null, it means p and q are found in different subtrees
        // Hence, the current node is their lowest common ancestor

        // If one of the left or right is non-null, return the non-null value
        // This means either one of p or q is found and we are returning up the recursive call stack
    }
};

• Recursion

/**
 * 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)
    {
        if (!root || root == p || root == q) return root;

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

        if (left && right) return root;
        return left ? left : right;
    }
};

• T: $O(N)$
• S: $O(N)$