LC: Closest Leaf in a Binary Tree - spiralgo/algorithms GitHub Wiki

Closest Leaf in a Binary Tree

The Essence:

If some parent contains this node somewhere in its subtree, then the closest leaf is either the closest leaf calculated by its subtree (including the node's subtree and parent's children's subtrees), or closest leaf in the other direction. This naturally leads to recursive structure comparing left-right subtrees for leaf-lengths.

As another approach, if the tree was converted into an undirected graph, the closest leaf simply would have been the leaf with the shortest path from the node.

Details:

The code implementation of both approaches and their code can be found here: https://github.com/spiralgo/algorithms/pull/327