Lowest Common Ancestor of a Binary Tree Leetcode Solution

Problem Statement

The Lowest Common Ancestor of a Binary Tree LeetCode Solution – “Lowest Common Ancestor of a Binary Tree” states that given the root of the binary tree and two nodes of the tree. We need to find the lowest common ancestor of these two nodes.

The Lowest Common Ancestor(LCA) of two nodes  p and q is the lowest node in the Binary Tree that has both  p and q as its descendants.

Example:

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

Explanation:

• Check the above diagram for a better understanding.
• The lowest node which has node 5 and node 1 as its descendants is a node with value 3.

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Explanation:

• Check the above diagram for a better understanding.
• The lowest common ancestor is a node with a value of 5 itself.

Approach

Idea:

1. The main idea to solve this problem is to use Recursion.
2. With the base case, when the root node becomes a null pointer return the root as it is.
3. Whenever we have the root node either equal to node p or equal to node q, we’ll return the root node as it is since the current node can be our lowest common ancestor.
4. Also, whenever we have the node returned from the left subtree and the right subtree are non-null pointers, we’ll return the current node which is our Lowest Common Ancestor.
5. When all the above cases fail, check if the node returned from the left subtree is not a null pointer return that node otherwise, return the node returned from the right subtree.

Code

Lowest Common Ancestor of a Binary Tree Leetcode C++ Solution:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr){
            return root;
        }
        TreeNode* l = lowestCommonAncestor(root->left,p,q);
        TreeNode* r = lowestCommonAncestor(root->right,p,q);
        if(root==p or root==q or (l!=nullptr and r!=nullptr)){
            return root;
        }
        return l==nullptr?r:l;
    }
};

Lowest Common Ancestor of a Binary Tree Leetcode Java Solution:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return root;
        }
        TreeNode l = lowestCommonAncestor(root.left,p,q);
        TreeNode r = lowestCommonAncestor(root.right,p,q);
        if(root==p || root==q || (l!=null && r!=null)){
            return root;
        }
        return l==null?r:l;
    }
}

Complexity Analysis for Lowest Common Ancestor of a Binary Tree Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we traverse the entire input tree once in the worst case where N = a total number of nodes in the tree.

Space Complexity

The space complexity of the above code is O(1) [without considering recursive stack space].