Lowest Common Ancestor of Binary Tree — Post-Order DFS

Problem 374 · Lowest Common Ancestor of a Binary Tree

Difficulty: Medium · Pattern: LCA Post-Order

Intuition

If current node is p or q, return it. Recurse left and right. If both sides return non-null, current node is LCA. Otherwise return the non-null side.

Solutions

# Python
def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q: return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    return root if left and right else left or right

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

// C++
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root||root==p||root==q) return root;
    auto l=lowestCommonAncestor(root->left,p,q);
    auto r=lowestCommonAncestor(root->right,p,q);
    return l&&r?root:l?l:r;
}

Complexity

Time: O(n)
Space: O(h)