So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'.
I can solve it in two ways -
Start at the given element and traverse up to the root of tree A - save the path and then follow the path down the second tree to the element.
Start at the root and traverse both trees at the same time using breadth-first search - once I find node A in tree A return the current node in tree B.
The complexity for the second approach will be O(N) as the worst case I could end up going through every node in the tree to find the element.
For the first approach is the complexity simply O(P) where P is the length of the path from the given node to the root? At most I will go up against P nodes and then down P nodes in tree B and 2P ~= P. I heard someone say it's Log(N) but I'm not sure how that could be.