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

Both sides previous revision Previous revision Next revision | Previous revision | ||

lowest_common_ancestor [2015/01/31 15:24] will |
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 algorithm works by tracing the path from the first node to the route of the tree using ''parent'' pointers. The path from the second node is 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 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. | 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.txt ยท Last modified: 2015/02/02 08:28 (external edit)