Given two identical DOM trees find same node in tree B
You are right, the complexity of the second algorithm is $O(P)$ where $P$ is the depth of the given vertex in the second tree. Notice that, without additional assumptions, it might very well be $P=\Omega(N)$ (think, e.g., of a path rooted in one endpoint where the given vertex is the other endpoint).
If the second tree is somehow &quot;balanced&quot;, for some reasonable definition of balanced* then its height will be at most $O(\log n)$, hence $P=O(\log n)$.
*Since your tree is not necessarily binary you'd have to provide a suitable definition of balanced. A sufficient condition for $P=O(N)$ would be for the heights of the two tallest subtrees rooted in two children of each node of the second tree to differ by at most an additive constant.