Lowest-Common-Ancestor
Description
This is a recursive algorithm that returns the Lowest Common Parent node of any two given nodes in a binary tree.
Complexity
Time: Worst 0(n)
Given the tree and inputs below, we recieve the following outputs:
// 3
// / \
// 11 5
// / \ / \
// 2 6 17 4
// / \ / \ / \ / \
// 7 9 13 21 14 8 19 1
LCA(7, 9) -> 2
LCA(6, 13) -> 6
LCA(4, 6) -> 3
LCA(17, 4) -> 5
LCA(21, 2) -> 11