0
Challenge · 45Trees

Paths and lowest common ancestor

Treesused in ~75% of apps

The last tree lesson, and the one that ties the tier together. Two nodes, one meeting point, and a four line function whose correctness is much more interesting than its length.

Core idea. The lowest common ancestor of two nodes is the deepest node that has both of them somewhere below it. Ask every node one question: did I find anything on my left, and did I find anything on my right? A node that gets yes from both sides is the meeting point, and there can only ever be one.
Playground, this isn't a screenshot
click any circle to find out what it is
Every circle is a node. The lines show which node hangs below which. Click one.

A tree is nodes joined by lines, with one node on top and no loops anywhere.

↑ play a little first, then dig in