Given two nodes a and b, write a function that returns their closest 'parent' node (must have both a and b as 'children').

Given two nodes a and b, write a function that returns their closest 'parent' node (must have both a and b as 'children').

if u have O(n) space you can do it in O(n) run time
traverse preorder the addresses of the nodes and store it.
then traverse inorder the addresses of the nodes and store it.
eg tree
a
b c
d e f
have PreOrder:a b d e c f
Inorder: d b e a c f
for two node ptrs eg d and c
mark the positions in inorder array and find first preorder ptr which separates it into two
different parts of Inorder array
for above example first preorder ptr is a which separates inorder into dbe and cf
so a is first commom ancester of d and c