This is a very common question appeared on interview sites, books. The solution they provided is either inefficient or hard to understand. I worked out a simple idea: return {null, p, q, common ancestor} four type of values then the recursion will be very easy to write, and the code runs in log(n)

To Pegasus: Your idea won't work. Usually tree nodes do not contain a parent pointer unless specified. So the recursion is top down manner.

Not binary search tree

Since it's not a binary search tree, you have to depth-first search the whole tree to find both nodes. When you find the nodes you save the path from the root to each. Then you just have to compare the two paths and find the last node in each that is the same. For instance, if the path to node G is A -> B -> C -> D -> G and the path to node H is A -> B -> E -> F -> H then the lowest common ancestor is B. Time complexity is O(n) where n is the number of nodes in the tree. Space complexity for a balanced tree is O(log(n)) since the paths can be the height of the tree.

1) Search for the node1 from root. Keep track of its path in a list. Time complexity: O(n) 2) Repeat the same for another node. 3) Now remove the common nodes from both of the list. 4) The last node before the match is your result. Time complexity: O(n) Space complexity: O(n)

Recursive call.