Find the lowest common ancestor in an unordered binary tree given two values in the tree.
Lowest common ancestor : the lowest common ancestor (LCA) of two nodes
win a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2_ 0 8 / \ 7 4
For the above tree, the LCA of nodes
LCA = Lowest common ancestor
Please note that LCA for nodes
- You are given 2 values. Find the lowest common ancestor of the two nodes represented by
- No guarantee that
val2exist in the tree. If one value doesn’t exist in the tree then return -1.
- There are no duplicate values.
- You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.