Lowest common ancestor of a binary tree

The Lowest common ancestor of a binary tree is a pretty fun problem. It goes a little like this:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Basically we have to find where the lowest common ancestor of two nodes are on a tree. Two nodes are ancestors if they share a tree value.

Immediate thoughts are to look at the depth nodes sit in on a tree, but it turns out this isn’t going to be helpful to us because depth is measured on the tree as a whole, not on the branches.

Another thought is to look at the left and the right nodes and see if two nodes share the same root… This seems promising.

Unlike my other solutions, I’ll be implementing this one in JavaScript. It should be easily translatable to other languages

A TreeNode is defined like this:

	

		

			Toggle
Numbering
			Copy
		
	

	
// Definition for a binary tree node.
function TreeNode(val) {
	this.val = val;
	this.left = this.right = null;
}

We’ll use recursion on this problem as we only need to check for child nodes that exist on the same tree.

	

		

			Toggle
Numbering
			Copy
		
	

	
var lowestCommonAncestor = function (root, p, q) {
	if (root === null) return root;
	if (root === p || root === q) return root;

	let leftRoot = lowestCommonAncestor(root.left, p, q);
	let rightRoot = lowestCommonAncestor(root.right, p, q);

	if (!leftRoot) return rightRoot;
	if (!rightRoot) return leftRoot;
	return root;
};