C++: Lowest Common Ancestor of a Binary Tree

Thought Process

To find the lowest common ancestor of two nodes (say 'p' & 'q') in a binary tree, we can use a recursive approach. If the current node is NULL or matches either 'p' or 'q', it is a potential LCA. Otherwise, we recursively search for 'p' and 'q' in the left & right subtrees. If both subtrees return non-null results, then the current node is LCA. Otherwise, we return the non-null result from either subtree. 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        // p & q can never be parent of root. So, if root==p/q then LCA would be root.
        if(root==NULL || root==p || root==q)
            return root;

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

        if(nod1!=NULL && nod2!=NULL)
            return root;
        else if(nod1!=NULL && nod2==NULL)
            return nod1;
        else if(nod1==NULL && nod2!=NULL)
            return nod2;
        else
            return NULL;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case, the space complexity is O(n).

Code copied!