Understanding the lowest common ancestor pattern
The lowest common ancestor of two nodes in a binary tree is the lowest node from the root, with both nodes as its descendants. Either of those nodes can also be the lowest common ancestor for itself and the other node. Consider the following examples of the lowest common ancestors for a pair of nodes in a binary tree.
The lowest common ancestor of two nodes in a binary tree.
The same idea can be extended to multiple nodes where the lowest common ancestor for all those nodes is the lowest node from the root such that all the other nodes are its descendants. Any of those nodes can itself be the lowest common ancestor of itself and the other nodes.
The lowest common ancestor of a set of nodes in a binary tree.
Let us look at the generic lowest common ancestor problem to understand it better.
The lowest common ancestor problem
Consider we are given a binary tree and a list of n nodes, and we need to find the lowest common ancestor of all these nodes.
A binary tree and a set of nodes.
Liking the course? Check our discounted plans to continue learning.