Problem Statement

Given the root of a binary tree and two nodes p and q return the lowest common ancestor (LCA) of these two nodes.

The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Examples

Example 1:

Input: p = 5, q = 1
        3
       / \
      5   1
     / \  / \
    6   2 0  8
       / \
      7   4
Output: 3

Explanation: The Lowest Common Ancestor of node 5 and 1 is 3 as it is the lowest node in the tree that has both 5 and 1 as descendants.

Example 2:

Input: p = 5, q = 4
        3
       / \
      5   1
     / \  / \
    6   2 0  8
       / \
      7   4
Output: 5

Explanation:
The Lowest Common Ancestor of nodes 5 and 4 is 5, as 5 is an ancestor of 4.

Example 3:

Input: p = 1, q = 2
        1
       /
      2
Output: 1

Explanation:
The Lowest Common Ancestor of nodes 1 and nodes 2 is 1, as 1 is the root and has 2 as a descendant.

Different Approaches

1️⃣ Depth First Search

Intuition:

Approach:

We solve this using Depth-First-Search (DFS) and recursion. The goal is to traverse the tree and identify where the two nodes p and q split in the subtree.

1. If the current node is null, return null.
2. If the current node matches either p or q, return the current node.
3. Recursively find p and q in the left and right subtrees.
   1. If one node is found in the left subtree and the other in the right subtree, the current node is their LCA.
   2. If both nodes are found in one subtree, return the subtree's result.
4. If neither node is found, return null.

Code:

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case
        if (root == NULL || root == p || root == q) {
            return root;
        }
        
        // Search in left and right subtrees
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        // Result
        if (left == NULL) {
            return right;
        } else if (right == NULL) {
            return left;
        } else { // Both left and right are not null, we found our result
            return root;
        }
    }
};

int main() {
    // Construct a simple binary tree
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    Solution solution;
    TreeNode* p = root->left; // Node with value 5
    TreeNode* q = root->right; // Node with value 1

    TreeNode* lca = solution.lowestCommonAncestor(root, p, q);
    cout << "Lowest Common Ancestor: " << lca->data << endl;

    return 0;
}

Complexity Analysis:

• Time complexity: O(N) where n is the number of nodes.
• Space complexity: O(N), auxiliary space.