What algorithm is this code using to find the lowest common ancestor of a binary tree?

Question

I found this solution on Leetcode while trying to solve this problem:

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Everyone on Leetcode seems to take for granted how this works. But I don't get it. What is going on here and what algorithm is this using to find the LCA of the binary tree?

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

There's no such thing as "the lowest common ancestor of a binary tree"; the problem actually asks you to find the lowest common ancestor of two nodes in a binary tree. — ruakh

Daniel Daniel · Accepted Answer · 2020-01-25T22:08:55

Quite simple:

The code looks at the root of the tree. If the root is p or q, then it returns it.

If it's not in the root, it searches in the left and right subtrees of the root, repeating the process until root is actually p or q.

Then comes the 3 last ifs.

if (left != null && right != null) return root;

This means that it found one of the nodes in the left subtree of the root and another in the right subtree of the root, hence root is the LCA.
if(left != null && right == null) return left;

This means that it found a node in the left subtree but no node in the right subtree, then the left node is the parent of the other node, hence the LCA.
if(right != null && left == null) return right;

This means that it found a node in the right subtree but no node in the left subtree, then the right node is the parent of the other node, hence the LCA.

Otherwise, the nodes aren't in the tree and there's no LCA.

What algorithm is this code using to find the lowest common ancestor of a binary tree?

1 Answers