0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Welcome to COMPUTERSCIENCE @SE. What is a) the complexity of getting from one node to its parent b) the complexity of getting from one node to all of its children in turn c) the height of the tree(s)? $\endgroup$
    – greybeard
    Sep 1, 2020 at 4:01
  • $\begingroup$ @greybeard thank you. a) would be constant to go from 1 node to its parent - a node simply has a .parentElement property. b) to visit all of a nodes children - it would be O(n) where n = number of children of that node. c) the height of the tree depends on if it's balanced or not. If it is, then it would be log(n) where n = nodes If it's not balanced - then it would be O(n) where n is the length of the longest path. b) $\endgroup$
    – CWright
    Sep 1, 2020 at 11:08

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.