This shows you the differences between two versions of the page.

Next revision | Previous revision | ||

lowest_common_ancestor [2015/01/29 09:39] will created |
lowest_common_ancestor [2015/02/02 08:28] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

====== Lowest common ancestor ====== | ====== Lowest common ancestor ====== | ||

- | The lowest common ancestor (LCA) of two nodes is the lowest node that has both nodes as node descendants. | + | The lowest common ancestor (LCA) of two nodes is the lowest node that has both nodes as descendants. The algorithm works by tracing the path from the first node to the root of the tree using ''parent'' pointers. The path from the second node is then traced upward until the first intersection with the path from the first node. This node is the lowest common ancestor. The first path is stored in a set such that insertion and test have $O(1)$ cost. |

+ | | ||

+ | The time and space complexity of this algorithm is $O(h)$ where $h$ is the height of the tree. This is $O(\log n)$ for balanced trees. | ||

[algorithm Lowest common ancestor] | [algorithm Lowest common ancestor] |

lowest_common_ancestor.1422553151.txt.gz · Last modified: 2015/02/02 08:24 (external edit)