algoadvance

Leetcode 236. Lowest Common Ancestor of a Binary Tree

Problem Statement

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Clarifying Questions

1. What kind of binary tree is it?

   • The binary tree is a general binary tree (not necessarily a binary search tree).

2. What should be returned if one or both nodes are not present in the tree?

   • Typically, we assume both nodes are present as per the problem constraints, but it’s good to confirm.

3. Can p and q be the same node?

   • Yes, it is possible for p and q to refer to the same node.

Strategy

To solve the problem, we can use a recursive approach:

1. Base Case:
   • If the current node is null, return null.
   • If the current node is either p or q, return the current node.
2. Recursively Search:
   • Recursively search the left and right subtrees.
3. Combine Results:
   • If both the left and right recursive calls return non-null values, it means p and q are found in different subtrees of the current node, so this node is their LCA.
   • If only one of the recursive calls returns a non-null value, that non-null return value is the LCA.
   • If both are null, return null.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // Recursively find LCA in the left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // If both left and right are non-null, this is the LCA
        if (left != null && right != null) {
            return root;
        }
        
        // If one is non-null, return the non-null node
        return left != null ? left : right;
    }
}

Time Complexity

• Time Complexity: O(N)
  • Where N is the number of nodes in the binary tree. This is because in the worst case, we traverse all nodes of the tree.
• Space Complexity: O(H)
  • Where H is the height of the tree. This is the space complexity of the recursion stack. In the worst case, H can be N (for a skewed tree). For a balanced tree, H is log(N).

This approach ensures we efficiently find the lowest common ancestor in a single traversal of the tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?