Lowest Common Ancestor of Two Nodes

medium tree dfs recursion

Problem

Given the root of a binary tree and two distinct values p and q guaranteed to be present, return the lowest node that has both in its subtree. Post-order DFS: at each node, return the first ancestor that finds both targets among its left and right subtrees.

Inputtree = [3,5,1,6,2,0,8], p = 5, q = 1

Output3

5 and 1 are siblings under 3.

tree (level-order)

def lca(root, p, q):
    if root is None or root.val == p or root.val == q:
        return root
    l = lca(root.left, p, q)
    r = lca(root.right, p, q)
    if l and r: return root
    return l or r

function lca(root, p, q) {
  if (!root || root.val === p || root.val === q) return root;
  const l = lca(root.left, p, q);
  const r = lca(root.right, p, q);
  if (l && r) return root;
  return l || r;
}

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

TreeNode* lca(TreeNode* root, int p, int q) {
    if (!root || root->val == p || root->val == q) return root;
    TreeNode* l = lca(root->left, p, q);
    TreeNode* r = lca(root->right, p, q);
    if (l && r) return root;
    return l ? l : r;
}

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