Lowest common ancestor

Find the lowest common ancestor (LCA) of two given nodes in the tree.

• Time: O(N)
• Space: O(1)

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

Find the lowest common ancestor (LCA) of two given nodes in the BST.

• Time: O(LogN)
• Space: O(1)

public TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > Math.max(p.val, q.val)) {
        return lcaBST(root.left, p, q);
    }
    if (root.val < Math.min(p.val, q.val)) {
        return lcaBST(root.right, p, q);
    }
    return root;
}