Given a binary tree find Lowest Common Ancestor LCA of two n

Given a binary tree, find Lowest Common Ancestor (LCA) of two nodes a and b.

No code, just explanation, visual, or some psudocode

Solution

Please find below the algorithm to find the Least Common Ancestor of two nodes a and b :

- Let a and b be the two nodes to find the Least Common Ancestor
- let root be the root node of the given binary tree
- let path1 and path2 be two arrays to store the path of a and b from root node respectively
- for path1 : starting from root, store all the nodes values till it reaches node a
- for path2 : starting from root, store all the nodes values till it reaches node b
- Now iterate through a loop, till it reaches the end of either path1 or path2
       > check if current element of path1 is equal to current element of path2
       > if both are equal, then just continue
       > if both are different, then just exit the loop
- now the loop iteration variable (value-1) will have the position till both the path1 and path2 are same(means same ancestor)
- now return the element of path1 or path2 at position value-1. This will be the Least Common Ancestor of both the nodes a and b