Lowest Common Ancestor of a Binary Tree II

class Solution {
public:
    TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
        bool found = false;

        function<TreeNode*(TreeNode*)> traverse = [&](TreeNode* current) {
            if (!current) return current;

            TreeNode* leftResult = traverse(current->left);
            TreeNode* rightResult = traverse(current->right);

            int matchCount = 0;
            if (current == p || current == q) matchCount++;
            if (leftResult != NULL) matchCount++;
            if (rightResult != NULL) matchCount++;
            if (matchCount == 2)
                found = true;

            if ((leftResult && rightResult) || (current == p) || (current == q)) return current;

            return leftResult ? leftResult : rightResult;
        };

        TreeNode* result = traverse(root);
        return found ? result : NULL;
    }
};

This solution addresses finding the Lowest Common Ancestor (LCA) of two nodes in a binary tree even when the nodes might not exist in the tree. The approach is implemented in C++ and involves a recursive traversal mechanism. Specifically, the method findLCA is designed to determine which node, if any, is the common ancestor of nodes p and q.

Here's the breakdown of the implemented logic:

• A recursive lambda function, traverse, is declared within findLCA. This lambda is used for depth-first tree traversal.
• During the traversal, the lambda checks each node to see if it is one of the targets (p or q) or if it received a target node from its left or right subtree.
• It utilizes three pointers for each node: the current node itself, and the results from traversing the left and right children.
• A local integer, matchCount, keeps track of how many of the nodes (current, left, or right) match either p or q.
• If matchCount equals two at any node, this node is marked as a potential LCA and found is set to true. This marking preempts further match searches since the LCA is resolved.
• The lambda returns:
  • the current node if it or both of its children are the target nodes,
  • the non-null child if only one child contains a target,
  • or null if neither the node nor its children are the targets.
• The final result of the traverse function is evaluated. If found is true, the function returns the marked LCA; otherwise, it returns NULL, indicating no LCA was found or one/both nodes do not exist in the tree.

The function ensures efficiency by combining the traversal and identification steps into a single recursive loop, avoiding the need to traverse the tree multiple times. In practice, this approach effectively finds the LCA under the constraints that both nodes might be absent from the tree. It also includes robust handling for cases where no LCA exists due to missing nodes, providing a clear distinction by returning NULL.

class Solution {

    boolean foundBoth = false;

    public TreeNode findAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode result = searchTree(root, p, q);
        return foundBoth ? result : null;
    }

    private TreeNode searchTree(TreeNode current, TreeNode p, TreeNode q) {
        if (current == null) return null;

        TreeNode leftSearch = searchTree(current.left, p, q);
        TreeNode rightSearch = searchTree(current.right, p, q);

        int matching = 0;
        if (current == p || current == q) matching++;
        if (leftSearch != null) matching++;
        if (rightSearch != null) matching++;
        if (matching == 2) foundBoth = true;

        if (current == p || current == q || (leftSearch != null && rightSearch != null)) return current;

        return leftSearch != null ? leftSearch : rightSearch;
    }
}

The code provided manipulates a binary tree to find the lowest common ancestor (LCA) of two nodes, referred to as p and q. It employs recursion to traverse the tree and identify the LCA only if both nodes are present in the tree. The process leverages a helper function searchTree alongside a boolean flag foundBoth to keep track of whether both nodes have been found during the traversal.

The workflow of the code is as follows:

• The main function findAncestor initializes the search by calling searchTree and provides the root of the binary tree and the two nodes p and q.
• The helper function searchTree recursively explores the tree. It performs a post-order traversal (explore left, explore right, process node):
  • It first recursively checks the left and right children of the current node.
  • It determines the number of matches among the current node, left child, and right child with either p or q.
  • If both nodes are identified at this stage (i.e., the sum of matches equals 2), the boolean flag foundBoth is set to true.
  • The function then decides whether the current node is the LCA based on conditions:
    • If either the current node is one of p or q, or both left and right recursive calls returned nodes (implying that p and q are found in different branches of this node), the current node is returned as the possible LCA.
  • If not conclusively determined, it propagates up the LCA found in either the left or right child, favoring non-null results.
• Finally, findAncestor checks the foundBoth flag. If true, it returns the node identified as the LCA. If either node p or q wasn't found during the traversal, it returns null.

This technique ensures that the function only returns the LCA if both target nodes p and q are indeed present in the provided binary tree. This method is efficient in terms of space complexity primarily using recursive stack space, and it ensures a thorough search through both left and right subtrees, meeting the conditions for identifying the lowest common ancestor in a binary tree.

class Solution:
    def findLCA(self, root: "TreeNode", node1: "TreeNode", node2: "TreeNode") -> "TreeNode":
        self.is_complete = False

        def traverse(current):
            if not current:
                return current
            left_child = traverse(current.left)
            right_child = traverse(current.right)

            num_conditions = 0
            if current in (node1, node2):
                num_conditions += 1
            if left_child:
                num_conditions += 1
            if right_child:
                num_conditions += 1
            if num_conditions == 2:
                self.is_complete = True
    
            if (left_child and right_child) or current in (node1, node2):
                return current
                
            return left_child or right_child

        result = traverse(root)
        return result if self.is_complete else None

The provided Python code defines a method to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree with an approach that guarantees both nodes exist in the tree.

The class Solution includes a method findLCA which takes three arguments: root, the root of the binary tree; node1, the first node to find the LCA for; and node2, the second node. The method initializes a boolean instance variable, is_complete, to track whether both nodes have been found during traversal.

The nested traverse function recursively explores the tree:

• It returns None if it reaches a leaf node (end of a branch).
• The function recursively calls itself for the left and right children of the current node.
• It counts conditions where the current node matches either of the target nodes or if the left or right child returns a non-null result, indicating one of the target nodes was found in that subtree.
• If exactly two conditions are met (meaning the current node is the lowest common ancestor), is_complete is set to True.
• If a path contains either target node or both children have the target nodes, the current node is returned as the LCA.
• Otherwise, the function returns either the left or right child's result, whichever is non-null.

The main function findLCA calls the traverse function starting from the root and assigns its output to result. The method concludes by checking is_complete; if true, it returns the LCA (result), otherwise, it returns None, indicating one or both target nodes are not present in the tree.

Key Details in This Implementation:

• The binary tree doesn't need to be balanced.
• Node existence is validated, ensuring the solution only returns an LCA if both nodes are present in the tree. This adds robustness to the function.
• The entire tree is potentially traversed in the worst case, making the time complexity O(n), where n is the number of nodes in the tree.

This code is ideally suited for scenarios where node existence in the tree needs verification before determining the LCA.