Daily bit(e) of C++ | Lowest common ancestor
Daily bit(e) of C++ #252, Common interview problem: Lowest common ancestor.
Today, we will look at a common C++ interview problem: Lowest common ancestor.
Given a binary tree and two (not necessarily different) nodes, return the node which is the lowest common ancestor to the two given nodes: https://en.wikipedia.org/wiki/Lowest_common_ancestor.
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/b6cbrqdc7.
Solution
Let’s consider the properties of a common ancestor of the nodes A and B.
We have two options: either one of the nodes, A or B, is this common ancestor, and the other node is in one of the two child subtrees, or the nodes A and B are in two different subtrees.
Notably, this means we are always looking for two matches (either we match the current node and one of the subtrees or both subtrees). This will even work when both nodes we are looking for are the same (in which case, the common ancestor is always the node itself).
With this logic, we can implement a straightforward post-order traversal.
