DSA 450 Notes

Problem Statement

Given a binary tree and two nodes p and q, find their Lowest Common Ancestor (LCA). The LCA is defined as the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Example:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

LCA(5, 1) = 3
LCA(5, 4) = 5
LCA(6, 4) = 5

Approach 1: Brute Force (Store Paths and Compare)

Intuition

Find the path from root to both nodes p and q. Then compare these paths to find the last common node, which is the LCA.

Algorithm

Find path from root to p
Find path from root to q
Compare paths from the start
Return the last node that's common in both paths

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;
        
        path.add(root);
        
        if (root == target) return true;
        
        if (findPath(root.left, target, path) || 
            findPath(root.right, target, path)) {
            return true;
        }
        
        // Backtrack
        path.remove(path.size() - 1);
        return false;
    }
    
    public TreeNode lcaBruteForce(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        
        // Find paths to both nodes
        findPath(root, p, pathP);
        findPath(root, q, pathQ);
        
        // Find last common node
        TreeNode lca = null;
        int i = 0;
        while (i < pathP.size() && i < pathQ.size()) {
            if (pathP.get(i) == pathQ.get(i)) {
                lca = pathP.get(i);
            } else {
                break;
            }
            i++;
        }
        
        return lca;
    }
}

Complexity Analysis

Time Complexity: O(n) - Two traversals to find paths
Space Complexity: O(n) - Store two paths, each can be O(n)

Approach 2: Optimal (Single Traversal)

Intuition

Use recursion. For each node, check if p or q is in its left or right subtree. If both subtrees contain one of p or q, current node is LCA. If only one subtree contains both, return that result.

Algorithm

If current node is null, p, or q, return it
Recursively search left and right subtrees
If both return non-null, current node is LCA
If only one returns non-null, return that (both are in same subtree)
If both return null, neither p nor q is in this subtree

java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public 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);
        
        // If both sides return non-null, current node is LCA
        if (left != null && right != null) {
            return root;
        }
        
        // Otherwise, return the non-null side (or null if both are null)
        return left != null ? left : right;
    }
}

Iterative Approach Using Parent Pointers

Complexity Analysis

Time Complexity: O(n) - Each node is visited at most once
Space Complexity: O(h) - Recursion stack depth, where h is height of tree

Key Takeaways

LCA Definition: Deepest node that is ancestor of both p and q
Key insight: If left and right subtrees each contain one of p/q, current node is LCA
Return value meaning: Non-null means p or q (or LCA) was found in that subtree
A node can be ancestor of itself - handles case where p is ancestor of q
For BST: LCA can be found more efficiently using BST properties

Find LCA in a Binary tree

Problem Statement

Approach 1: Brute Force (Store Paths and Compare)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Single Traversal)

Intuition

Algorithm

Iterative Approach Using Parent Pointers

Complexity Analysis

Key Takeaways