Cracking The Coding Interview Together – Problem 4.8: Finding the First Common Ancestor in a Binary Tree

As senior engineers, we often find ourselves navigating complex hierarchical data. Think file systems, organizational charts, or even the DOM of a web page. A fundamental challenge in these structures is understanding relationships, specifically finding the 'meeting point' of two distinct entities. This isn't just an academic exercise; it's a core piece of business logic that underpins features like permission systems, content categorization, or even merge conflict resolution in version control. Today, we're tackling a classic problem that forces us to think deeply about tree traversals and space efficiency: finding the First Common Ancestor (FCA) of two nodes in a binary tree without relying on extra data structures. Our shared goal is to design and implement a robust, efficient solution that respects these constraints, giving us a powerful tool for our engineering toolkit.

Problem Statement

The challenge before us is clear: Given the root of a binary tree and two distinct nodes, p and q, we need to find their First Common Ancestor. The critical constraint here is that we cannot store additional nodes in any data structure to solve this. This means no lists, no sets, no maps to track paths or visited nodes. We must operate within the confines of the tree structure itself, aiming for an elegant and space-optimized solution.

Analyze the Problem Together

Let's dissect this problem. We're dealing with a generic binary tree, not necessarily a Binary Search Tree (BST), which means node values don't impose any ordering constraints. Crucially, we don't have parent pointers, a common convenience that simplifies many tree problems. The 'Aha!' conflict arises from the space constraint: how do we determine if p and q are in different subtrees of a given node, or if one is an ancestor of the other, without explicitly storing the paths from the root?

Consider naive approaches:

• Path Storage: We could traverse from the root to p and q, storing each path in a list. Then, we'd compare the two lists to find the last common node. This is straightforward but violates our 'no additional data structures' rule, as the lists would store nodes.
• Parent Pointers (if available): If nodes had parent pointers, we could traverse up from p and q, marking visited nodes (e.g., in a HashSet). The first node encountered by both traversals would be the FCA. Again, this uses an additional data structure (the HashSet) and assumes parent pointers, which we don't have.

These approaches highlight why the constraint is so important: it pushes us towards a more sophisticated, often recursive, solution. The architectural choice for problems like this, especially without parent pointers or extra space, often leans towards a recursive, bottom-up traversal. The intuition is that if a node's left subtree contains one target and its right subtree contains the other, then the current node must be their FCA. If both targets are found in the same subtree, the FCA must be deeper within that subtree. This recursive pattern allows us to 'bubble up' information about found nodes without explicitly storing paths.

Questions for the Interviewer

Before we dive into coding, a senior engineer always clarifies assumptions. Here are a few questions we'd pose to ensure we're solving the right problem:

1. Are p and q guaranteed to be present in the tree? (For this problem, we'll assume they are. If not, our function would need to handle cases where one or both are missing, perhaps by returning null or throwing an exception.)
2. What if p or q is the root of the tree? (Our solution should naturally handle this, but it's good to confirm expectations.)
3. What if one node is an ancestor of the other (e.g., p is an ancestor of q)? (In this scenario, p itself would be the First Common Ancestor. Our algorithm should correctly identify this.)
4. Is this a Binary Search Tree (BST) or a general Binary Tree? (The problem statement implies a general binary tree, which is a harder constraint than a BST where ordering could be leveraged.)

Think About the Solution

Our high-level strategy will be a recursive depth-first traversal. We'll define a function, let's call it findFCA, that takes the current node and the two target nodes (p and q) as arguments. This function will return the FCA if found within the subtree rooted at the current node, or one of p or q if it's found, or null if neither is found.

Here's the core logic we'll implement:

• Base Case: If the current node is null, or if it's p or q, we return the current node. This is crucial because if we find p or q, that node itself could be the FCA (if the other node is in its subtree) or part of the path leading to the FCA.
• Recursive Step:
  1. Recursively call findFCA on the left child. Let the result be leftResult.
  2. Recursively call findFCA on the right child. Let the result be rightResult.
• Combine Results:
  • If both leftResult and rightResult are non-null, it means p was found in one subtree and q in the other. Therefore, the current node is their First Common Ancestor. We return the current node.
  • If only leftResult is non-null, it means both p and q (or just one of them) were found in the left subtree. So, the FCA must be leftResult. We return leftResult.
  • If only rightResult is non-null, similarly, the FCA must be rightResult. We return rightResult.
  • If both leftResult and rightResult are null, neither p nor q was found in this subtree. We return null.

This approach elegantly handles all cases: when p or q is the root, when one is an ancestor of the other, and when they are in separate branches.

Write Code and Explain

Let's translate this logic into production-ready Java code. We'll define a simple TreeNode class and then our findFCA method.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class FirstCommonAncestor {

    /**
     * Finds the first common ancestor of two nodes in a binary tree.
     * This solution avoids storing additional nodes in a data structure
     * by using a recursive, bottom-up approach.
     *
     * @param root The root of the binary tree.
     * @param p    The first target node.
     * @param q    The second target node.
     * @return The first common ancestor of p and q, or null if not found (or if root is null).
     */
    public TreeNode findFCA(TreeNode root, TreeNode p, TreeNode q) {
        // Base Case 1: If the current node is null, we can't find p or q here.
        if (root == null) {
            return null;
        }

        // Base Case 2: If the current node is one of the target nodes (p or q),
        // then this node is the "first" point of interest on the path from the root.
        // It could be the FCA if the other node is in its subtree, or it's part of the path to the FCA.
        if (root == p || root == q) {
            return root;
        }

        // Recursively search for p and q in the left subtree.
        TreeNode leftResult = findFCA(root.left, p, q);

        // Recursively search for p and q in the right subtree.
        TreeNode rightResult = findFCA(root.right, p, q);

        // Case 1: Both p and q were found in different subtrees.
        // If leftResult is not null AND rightResult is not null,
        // it means p was found in one subtree and q in the other.
        // Therefore, the current 'root' is their First Common Ancestor.
        if (leftResult != null && rightResult != null) {
            return root;
        }

        // Case 2: Only one of p or q was found, and it was in the left subtree.
        // This implies that if the other node exists, it must also be in the left subtree,
        // or 'leftResult' itself is the FCA (e.g., if leftResult is p, and q is in p's subtree).
        // So, we propagate leftResult upwards.
        if (leftResult != null) {
            return leftResult;
        }

        // Case 3: Only one of p or q was found, and it was in the right subtree.
        // Similar to Case 2, we propagate rightResult upwards.
        if (rightResult != null) {
            return rightResult;
        }

        // Case 4: Neither p nor q was found in either the left or right subtrees.
        // This means they are not in the subtree rooted at 'root', so we return null.
        return null;
    }

    // Helper method to build a sample tree for testing
    public static TreeNode buildSampleTree() {
        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);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        return root;
    }

    public static void main(String[] args) {
        FirstCommonAncestor solver = new FirstCommonAncestor();
        TreeNode root = buildSampleTree();

        // Example 1: p=5, q=1. Expected FCA: 3 (root)
        TreeNode p1 = root.left; // Node with value 5
        TreeNode q1 = root.right; // Node with value 1
        System.out.println("FCA of " + p1.val + " and " + q1.val + ": " + solver.findFCA(root, p1, q1).val);

        // Example 2: p=5, q=4. Expected FCA: 5
        TreeNode p2 = root.left; // Node with value 5
        TreeNode q2 = root.left.right.right; // Node with value 4
        System.out.println("FCA of " + p2.val + " and " + q2.val + ": " + solver.findFCA(root, p2, q2).val);

        // Example 3: p=6, q=7. Expected FCA: 5
        TreeNode p3 = root.left.left; // Node with value 6
        TreeNode q3 = root.left.right.left; // Node with value 7
        System.out.println("FCA of " + p3.val + " and " + q3.val + ": " + solver.findFCA(root, p3, q3).val);

        // Example 4: p=0, q=8. Expected FCA: 1
        TreeNode p4 = root.right.left; // Node with value 0
        TreeNode q4 = root.right.right; // Node with value 8
        System.out.println("FCA of " + p4.val + " and " + q4.val + ": " + solver.findFCA(root, p4, q4).val);
    }
}

Let's walk through the findFCA method step-by-step to solidify our understanding:

1. if (root == null): This is our first base case. If we've traversed past a leaf node or started with an empty tree, there's nothing to find, so we return null.
2. if (root == p || root == q): This is our second, crucial base case. If the current root node is one of our target nodes (p or q), we immediately return root. Why? Because this node is the first point on the path from the original tree root where we encounter one of our targets. It could be the FCA itself (if the other target is in its subtree), or it's part of the path to the FCA.
3. TreeNode leftResult = findFCA(root.left, p, q);: We recursively call findFCA on the left child. leftResult will hold either null (if neither p nor q is in the left subtree), p (if p is found in the left subtree and q is not), q (if q is found in the left subtree and p is not), or the actual FCA of p and q if both are found within the left subtree.
4. TreeNode rightResult = findFCA(root.right, p, q);: We do the same for the right child, storing the result in rightResult.
5. if (leftResult != null && rightResult != null): This is the 'Aha!' moment. If both leftResult and rightResult are non-null, it means we found one target (p or q) in the left subtree and the other target in the right subtree. The current root node is therefore the first node where their paths diverge, making it their First Common Ancestor. We return root.
6. if (leftResult != null): If only leftResult is non-null, it implies that either both p and q are located within the left subtree (and leftResult is their FCA), or one of them is leftResult itself and the other is in its subtree. In any case, the FCA must be leftResult or deeper within that branch, so we propagate leftResult upwards.
7. if (rightResult != null): Similarly, if only rightResult is non-null, we propagate rightResult upwards.
8. return null;: If neither leftResult nor rightResult is non-null, it means neither p nor q was found in the subtree rooted at the current root. We return null to indicate their absence.

Time & Space Complexity

Understanding the performance characteristics of our solution is paramount.

• Time Complexity: O(N)
  In the worst case, our algorithm might visit every node in the binary tree exactly once. Each node involves constant time operations (checking for null, comparing references, making recursive calls). Therefore, the time complexity is directly proportional to the number of nodes, N.
• Space Complexity: O(H)
  The space complexity is determined by the maximum depth of the recursion stack. In the worst-case scenario of a skewed tree (where the tree resembles a linked list), the height H can be equal to the number of nodes N. In a balanced tree, H would be log N. Thus, the space complexity is O(H), where H is the height of the tree. This adheres to our constraint of not storing additional nodes in auxiliary data structures, as the recursion stack is part of the function call overhead.

Why This Problem Matters (The Senior Perspective)

This problem, while seemingly abstract, is a fantastic microcosm of real-world challenges we face as senior engineers. Hierarchical data structures are ubiquitous, and understanding relationships within them is critical.

• Real-world Applications:
  • File Systems: Imagine finding the common directory for two files. This is exactly the FCA problem.
  • Organizational Charts: Determining the lowest common manager for two employees.
  • DOM Trees: In web development, finding the closest common parent element for two distinct HTML elements.
  • Version Control Systems: When merging two branches, finding their common ancestor commit is a core operation.
  • Network Routing: Identifying the common router or subnet for two IP addresses in a hierarchical network topology.
• Architectural Patterns: This solution exemplifies the power of recursive traversal and divide and conquer. We break down the problem into smaller, identical subproblems (finding p and q in subtrees) and then combine their results. This pattern is fundamental to solving many tree and graph problems efficiently.
• Production Considerations:
  • Scalability: For extremely deep trees, a recursive solution in languages like Java can hit a StackOverflowError. While our solution is optimal given the constraints, in a production system with potentially millions of nodes, an iterative approach (if parent pointers were available or if we could use a stack explicitly) might be preferred to manage stack depth.
  • Concurrency: If the tree structure is mutable (nodes can be added or removed) and accessed concurrently, our findFCA method would need to be made thread-safe. This could involve using locks or, ideally, designing the tree as an immutable data structure for read-heavy operations.
  • Data Integrity: Our solution assumes p and q exist in the tree. In a production system, we'd add checks to gracefully handle cases where one or both nodes are not found, perhaps by returning null and logging a warning.
  • Performance for Repeated Queries: If FCA queries are extremely frequent on a static tree, more advanced data structures like LCA (Lowest Common Ancestor) data structures (e.g., using Euler tour + Range Minimum Query (RMQ) or binary lifting) could pre-process the tree in O(N log N) or O(N) time and answer queries in O(1) or O(log N) time. However, these solutions typically involve storing additional information, violating our problem's specific constraint. Our current solution is optimal for a single query without extra storage.

Final Thoughts

Mastering problems like the First Common Ancestor is a testament to your ability to think critically about data structures and algorithms under tight constraints. We've seen how a well-crafted recursive solution can elegantly solve a complex problem with optimal time and space efficiency, all while avoiding auxiliary data structures. This pattern of 'bubbling up' information from subproblems is incredibly powerful. Keep practicing these foundational concepts, as they are the building blocks for designing robust and scalable systems. What other tree problems do you think could benefit from a similar recursive, space-optimized approach? Share your thoughts!