Lowest Common Ancestor in Binary Tree in DSA C++

Mental Model

Find the shared parent node where two nodes meet first when moving up the tree.

Analogy: Like finding the closest common boss for two employees in a company hierarchy tree.

       1
      / \
     2   3
    / \   \
   4   5   6

Dry Run Walkthrough

Input: Binary tree: 1->2,3; 2->4,5; 3->null,6; Find LCA of nodes 4 and 5

Goal: Find the lowest node that is an ancestor of both 4 and 5

Step 1: Start at root node 1, check left and right subtrees for nodes 4 and 5

At node 1: searching left subtree -> 2, right subtree -> 3

Why: We begin from the top to find where both nodes appear in subtrees

Step 2: Move to left child 2, check left subtree for node 4

At node 2: left child -> 4, right child -> 5

Why: Node 2 is parent of 4 and 5, so check its children

Step 3: Find node 4 at left child of 2, return node 4 up

Found node 4 at left child of 2

Why: One target node found, return it to parent call

Step 4: Find node 5 at right child of 2, return node 5 up

Found node 5 at right child of 2

Why: Second target node found, return it to parent call

Step 5: At node 2, both left and right returned non-null (4 and 5), so node 2 is LCA

LCA found at node 2

Why: Both nodes found in different subtrees of 2, so 2 is their lowest common ancestor

Result:

2 is the lowest common ancestor of nodes 4 and 5

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return nullptr; // base case: empty subtree
    if (root == p || root == q) return root; // found one target node

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

    if (left != nullptr && right != nullptr) return root; // both nodes found in different subtrees
    if (left != nullptr) return left; // both nodes in left subtree
    return right; // both nodes in right subtree or none found
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    TreeNode* p = root->left->left; // node 4
    TreeNode* q = root->left->right; // node 5

    TreeNode* lca = lowestCommonAncestor(root, p, q);
    if (lca != nullptr) {
        cout << lca->val << "\n";
    } else {
        cout << "No common ancestor found\n";
    }
    return 0;
}

if (root == nullptr) return nullptr;

stop if subtree is empty

if (root == p || root == q) return root;

return node if it matches one target

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

search left subtree for targets

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

search right subtree for targets

if (left != nullptr && right != nullptr) return root;

if targets found in both subtrees, current node is LCA

if (left != nullptr) return left;

if both targets in left subtree, return left result

return right;

otherwise return right subtree result

Output

2

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to storing parent pointers and paths, this method uses no extra memory for parent maps and is simpler

Edge Cases

Empty tree (root == nullptr)

Function returns nullptr indicating no common ancestor found

DSA C++

if (root == nullptr) return nullptr;

One node is ancestor of the other

Ancestor node is returned as LCA

DSA C++

if (root == p || root == q) return root;

Tree with only one node which is both p and q

That node is returned as LCA

DSA C++

if (root == p || root == q) return root;

When to Use This Pattern

When asked to find the shared ancestor of two nodes in a tree without parent pointers, use the recursive LCA pattern to find the lowest common ancestor efficiently.

Common Mistakes

Mistake: Returning the first found node without checking both subtrees
Fix: Check both left and right subtree results to confirm both nodes are found before returning current node as LCA

Mistake: Not handling the case when one node is ancestor of the other
Fix: Return current node immediately if it matches either target node

Summary

Finds the lowest node in a binary tree that is ancestor to two given nodes.

Use when you need to find the closest shared parent of two nodes in a tree without parent links.

The key insight is that if both nodes are found in different subtrees of a node, that node is their lowest common ancestor.