Lowest Common Ancestor Of A Binary Tree

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode* left;
 *     TreeNode* right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right) {
            return root;
        }
        
        return left ? left : right;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if root is None or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left is None:
            return right
        elif right is None:
            return left
        else:
            return root

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }
    
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    if (left != NULL && right != NULL) {
        return root;
    } else if (left != NULL) {
        return left;
    } else {
        return right;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        
        TreeNode left = LowestCommonAncestor(root.left, p, q);
        TreeNode right = LowestCommonAncestor(root.right, p, q);
        
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

var lowestCommonAncestor = function(root, p, q) {
    if (!root || root === p || root === q) {
        return root;
    }
    
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    if (left && right) {
        return root;
    }
    
    return left || right;
};

Explanation

To solve this coding challenge, we need to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree. The LCA of two nodes p and q in a binary tree is defined as the deepest (lowest) node that has both p and q as descendants. This challenge involves traversal of the binary tree and needs an approach that explores all possible paths to identify the relationship between the nodes. We will employ a recursive depth-first search (DFS) strategy that allows us to explore every node in the tree. Below is a detailed explanation of the algorithm we can use to solve this problem:

Base Case:

If the current node is
null

(None), return
null

. This signifies that we have reached a leaf node and didn't find either of the nodes
p

or
q

.
If the current node matches either
p

or
q

, return the current node. This indicates that one of the target nodes has been found.

Recursive Search:

Recursively search the left and right subtrees for the nodes
p

and
q

.
If both the left and right subtrees return non-null values, it means both
p

and
q

have been found in different branches, hence the current node is the LCA.
If only one of the subtrees returns a non-null value, return that non-null value as it indicates that both
p

and
q

are located in the same subtree or one is a descendant of the other.

The algorithm continues this recursive search until the entire tree is traversed.

Detailed Steps in Pseudocode

Recursive function definition: Define a function
findLCA

which accepts the current
node

, and target nodes
p

and
q

.
Base conditions:

If
node is None

, return
None

.
If
node is p or q

, return
node

.

Recursive search:

Search the left subtree:
leftResult = findLCA(node.left, p, q)
Search the right subtree:
rightResult = findLCA(node.right, p, q)
If both
leftResult

and
rightResult

are non-null, then
node

is the LCA.
If only one of
leftResult

or
rightResult

is non-null, return that result.
If both are null, return
None

.

Here is the pseudocode with comments:

                                            
# Recursive function to find the lowest common ancestor of nodes p and q
def findLCA(node, p, q):
    # Base Case: if the current node is None, return None
    if node is None:
        return None
    
    # If the current node matches p or q, return the current node
    if node == p or node == q:
        return node
    
    # Recursively search for LCA in the left subtree
    leftResult = findLCA(node.left, p, q)
    
    # Recursively search for LCA in the right subtree
    rightResult = findLCA(node.right, p, q)

    # If both leftResult and rightResult are non-null, the current node is the LCA
    if leftResult is not None and rightResult is not None:
        return node
    
    # If either leftResult or rightResult is non-null, return the non-null result
    if leftResult is not None:
        return leftResult
    else:
        return rightResult

# Function to initiate the LCA finding process
def lowestCommonAncestor(root, p, q):
    return findLCA(root, p, q)

The above pseudocode provides a detailed recursive solution for finding the lowest common ancestor in a binary tree. This solution ensures that every necessary possible path is explored, guaranteeing the correct result for the LCA identification problem. The comments within the code explain each step to make sure the logic is clear and understandable.