Given two identical DOM trees find same node in tree B

Question

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 -

1. 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.

2. 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.

Answer 1

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 "balanced", 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.