Lowest Common Ancestor in a Binary Tree
concept
The lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants, where n1 and n2 are the nodes for which we wish to find the LCA(Lowest Common Ancestor). Hence, the LCA of a binary tree with nodes n1 and n2 is the shared ancestor of n1 and n2 that is located farthest from the root.
GO code
output
B and G have a first common ancestor A
D and E have a first common ancestor B
big-O time
O(N)
The tree is traversed twice, and then path arrays are compared.