LCA in BT

Intuition

Finding the Lowest Common Ancestor (LCA) of two nodes in a binary tree requires determining the closest node that is an ancestor to both given nodes. The LCA can be identified as one of the following: it may be located within the left subtree, the right subtree, or it might be the root node itself if the two nodes are distributed across both subtrees. The fundamental idea is that the LCA is the deepest node that serves as an ancestor to both target nodes, representing the point where their paths to the root diverge.

Approach

Start by checking if the current root node is null or matches one of the target nodes (x or y). If the root is null or matches either target node, then return the root, as it could potentially be the LCA or simply indicate the end of the search path.
Perform a recursive search in the left subtree to find the nodes x and y. This involves calling the LCA function on the left child of the current root.
Similarly, perform a recursive search in the right subtree. This entails calling the LCA function on the right child of the current root.
After completing the recursive searches, analyze the results of both subtree searches. If both recursive calls return non-null values, it implies that one target node was found in each subtree. Consequently, the current root node must be the LCA, as it is the common ancestor of both nodes.
If only one of the subtree searches returns a non-null result, it indicates that both target nodes are located within the same subtree. In this case, return the non-null result, which represents the LCA found in that subtree.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), 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;
        }
        
        // Search in left and right subtrees
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        // Result
        if (left == NULL) {
            return right;
        } else if (right == NULL) {
            return left;
        } else { // Both left and right are not null, we found our result
            return root;
        }
    }
};

int main() {
    // Construct a simple binary tree
    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);

    Solution solution;
    TreeNode* p = root->left; // Node with value 5
    TreeNode* q = root->right; // Node with value 1

    TreeNode* lca = solution.lowestCommonAncestor(root, p, q);
    cout << "Lowest Common Ancestor: " << lca->data << endl;

    return 0;
}
// Definition for a binary tree node.
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { 
        data = val; 
        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;
        }
        
        // Search in left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // Result
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else { // Both left and right are not null, we found our result
            return root;
        }
    }

    public static void main(String[] args) {
        // Construct a simple binary tree
        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);

        Solution solution = new Solution();
        TreeNode p = root.left; // Node with value 5
        TreeNode q = root.right; // Node with value 1

        TreeNode lca = solution.lowestCommonAncestor(root, p, q);
        System.out.println("Lowest Common Ancestor: " + lca.data);
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        # Base case
        if root is None or root == p or root == q:
            return root
        
        # Search in left and right subtrees
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        # Result
        if left is None:
            return right
        elif right is None:
            return left
        else: # Both left and right are not null, we found our result
            return root

if __name__ == "__main__":
    # Construct a simple binary tree
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)

    solution = Solution()
    p = root.left  # Node with value 5
    q = root.right  # Node with value 1

    lca = solution.lowestCommonAncestor(root, p, q)
    print("Lowest Common Ancestor:", lca.data)
// Definition for a binary tree node.
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    lowestCommonAncestor(root, p, q) {
        // Base case
        if (root === null || root === p || root === q) {
            return root;
        }
        
        // Search in left and right subtrees
        let left = this.lowestCommonAncestor(root.left, p, q);
        let right = this.lowestCommonAncestor(root.right, p, q);
        
        // Result
        if (left === null) {
            return right;
        } else if (right === null) {
            return left;
        } else { // Both left and right are not null, we found our result
            return root;
        }
    }
}

// Example usage
let 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);

let solution = new Solution();
let p = root.left; // Node with value 5
let q = root.right; // Node with value 1

let lca = solution.lowestCommonAncestor(root, p, q);
console.log("Lowest Common Ancestor:", lca.data);

Complexity Analysis

Time complexity: O(N) where n is the number of nodes.

Space complexity: O(N), auxiliary space.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts