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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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