algorithm

Lowest common ancestor of a Binary Tree

Introduction#

Lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in the tree that has both n1 and n2 as descendants.

Finding lowest common ancestor

Consider the tree:

enter image description here

Lowest common ancestor of nodes with value 1 and 4 is 2

Lowest common ancestor of nodes with value 1 and 5 is 3

Lowest common ancestor of nodes with value 2 and 4 is 4

Lowest common ancestor of nodes with value 1 and 2 is 2

This modified text is an extract of the original Stack Overflow Documentation created by the contributors and released under CC BY-SA 3.0 This website is not affiliated with Stack Overflow