Template Function ADS::lowestCommonAncestor

• Defined in File BinaryTreeAlgorithms.h

Function Documentation

template<ParentBinaryNode N>
N ADS::lowestCommonAncestor(N u, N v)

lowestCommonAncestor(): the deepest node that is an ancestor of both u and v, each node being an ancestor of itself; O( h ) time, O( 1 ) space

Pre:

u and v are nodes of the same tree

Post:

an ancestor of u and of v, none of whose children is one