Lowest common ancestor (general binary tree)

Find the deepest node with both targets beneath it, without relying on any BST ordering.

The idea

With no ordering to guide the search, every node must be visited. Search the left and right subtrees for p and q independently. If both sides report back a find, the current node sits between them and is the answer. If only one side finds something, pass that result up unchanged; it might be the answer, or might still need to rise further.

Code

public static TreeNode Lca(TreeNode node, TreeNode p, TreeNode q) {
    if (node == null || node == p || node == q) return node;
    TreeNode left = Lca(node.left, p, q);
    TreeNode right = Lca(node.right, p, q);
    if (left != null && right != null) return node;
    return left ?? right;
}

Tips

• Returning the node itself the moment it equals p or q (without searching its own subtrees) is what lets a deeper match win over a shallower one.

In the .NET library

Unlike the BST version, this works on any binary tree because it never compares values to decide direction, only tests for equality with p or q.