Solution For Lowest Common Ancestor Of A Binary Tree

Problem Description:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Example:

Input:
3
/ \
5 1
/ \ / \
6 2 7 4

p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Solution:

To solve this problem, we need to traverse the binary tree and find the paths from the root to the two nodes p and q. Once we have the paths, we can find the last common node in the two paths, which will be the LCA.

For traversing the binary tree, we can use depth-first search (DFS) algorithm. We can define a recursive function findPath(root, node, path) that will take a root node, a node to find, and a list path that will contain the path from root to node. The function will return True if the node is found, False otherwise.

The main function lowestCommonAncestor(root, p, q) will call the findPath function twice to find the paths from the root to the two nodes p and q. Then it will iterate over the paths and find the last common node in the two paths.

Here is the Python code:

“`
class TreeNode:
def init(self, x):
self.val = x
self.left = None
self.right = None

def findPath(root, node, path):
if not root:
return False

path.append(root)

if root == node:
    return True

if (root.left and findPath(root.left, node, path)) or \
   (root.right and findPath(root.right, node, path)):
    return True

path.pop()
return False

def lowestCommonAncestor(root, p, q):
path1 = [] findPath(root, p, path1)

path2 = []
findPath(root, q, path2)

i = 0
while i < len(path1) and i < len(path2) and path1[i] == path2[i]:
    i += 1

return path1[i-1] if i > 0 else None

“`

Time Complexity:

The time complexity of this method is O(N) where N is the number of nodes in the binary tree. In the worst case, we might need to traverse all the nodes to find the LCA.

Space Complexity:

The space complexity of this method is O(N) because we are storing the path lists for two nodes, which can have at most N nodes in total.

Step by Step Implementation For Lowest Common Ancestor Of A Binary Tree

/**
 * 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) {
        
        // Base case 
        if (root == null || root == p || root == q) 
            return root; 
  
        // Look for keys in left and right subtrees 
        TreeNode left = lowestCommonAncestor(root.left, p, q); 
        TreeNode right = lowestCommonAncestor(root.right, p, q); 
  
        // If both of the above calls return Non-NULL, then one key 
        // is present in once subtree and other is present in other, 
        // So this node is the LCA 
        if (left != null && right != null) 
            return root; 
  
        // Otherwise check if left subtree or right subtree is LCA 
        return (left != null) ? left : right; 
    }
}

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base case
        if not root or root == p or root == q:
            return root
        
        # Recursive call on left and right subtrees
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        # If both left and right subtrees have a node that is the LCA, 
        # then the current root is the LCA
        if left and right:
            return root
        # Otherwise, the left subtree or the right subtree has the LCA, 
        # so return that node
        elif left:
            return left
        else:
            return right

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 
 // recursive solution
var lowestCommonAncestor = function(root, p, q) {
    // if root is null or root is p or root is q, then root is the LCA
    if (!root || root === p || root === q) {
        return root;
    }
    
    // get LCA of left and right subtree
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    
    // if left and right are both not null, then root is the LCA
    if (left && right) {
        return root;
    }
    
    // otherwise, return the LCA from the subtree that is not null
    return left ? left : right;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case
        if (root == NULL || root == p || root == q) return root;
        
        // Look for keys in left and right subtrees
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        // If both of the above calls return Non-NULL, then one key
        // is present in once subtree and other is present in other,
        // So this node is the LCA
        if (left != NULL && right != NULL) return root;
        
        // Otherwise check if left subtree or right subtree is LCA
        return (left != NULL) ? left : 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) {
        //Check if either p or q is the root. If so, return root.
        if(root == p || root == q){
            return root;
        }
        
        //Check if p and q are on different sides of the root.
        //If they are, return root. Otherwise, keep searching.
        if((root.val - p.val) * (root.val - q.val) <= 0){
            return root;
        }
        else if(root.val < p.val){
            return LowestCommonAncestor(root.right, p, q);
        }
        else{
            return LowestCommonAncestor(root.left, p, q);
        }
    }
}