Page 33 - Algorithms Notes for Professionals
P. 33

Chapter 8: Lowest common ancestor of a

       Binary Tree




       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.

       Section 8.1: Finding lowest common ancestor


       Consider the tree:
















       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


















































       colegiohispanomexicano.net – Algorithms Notes                                                            29
   28   29   30   31   32   33   34   35   36   37   38