The lowest common ancestor (LCA) of nodes ‘a’ & ‘b’ of a tree is the lowest node in the tree that has node ‘a’ & node ‘b’ as descendants.
Below are some of the algorithmic techniques used for finding the lowest common ancestor of 2 nodes in a binary / multinode tree.
| Tree Type | Algorithm | Algorithm Gist | Time Complexity |
|---|---|---|---|
| Binary Tree | Recursive tree-traversal | 1. Recursively traverse the left sub-tree and right sub-tree and return each node to its parent.2. If the nodes (not NULL) returned to the parent come from the left and the right sub-tree, the parent is the lowest common ancestor.3. If both nodes come from the same sub-tree then one of the nodes is the lowest common ancestor. | O(N), where N is the number of nodes in the tree. |
| Tree with multiple nodes | Upward tree-traversal | 1. Traverse upward from each node towards the root node and keep track of the visited node(s).2. Traverse from the second node towards the root, if a visited node is found on the way, it evidently is the lowest common ancestor. | O(N), where N is the number of nodes in the tree. |
| Tree with multiple nodes | Hop 1 level up and move closer to the other node | 1. Get parent of every node using a depth-first traversal..2. Hop 1 level up from the node that is lower in the tree towards the upper node. 3. When the lower node is same as the upper node, the LCA of the two nodes has been found. | O(N), where N is the number of nodes in the tree. |