Skip to main content
Computer Science

Return to Question

Post Timeline

Grammatical errors solved
Source Link
edit approved Jun 27, 2021 at 23:39
Hedayatullah Sarwary
edit approved Jun 27, 2021 at 23:39
Hedayatullah Sarwary
  • 259
  • 1
  • 4
  • 9

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-first search - once I find nodeAnode A in tree A return the current node in treeBtree 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 treeBtree B and 2P ~= P. I heard someone say it's Log(N) but I'm not sure how that could be.

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 nodeA in tree A return the current node in treeB.

The complexity for the second approach will be O(N) as 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 P nodes and then down P nodes in treeB and 2P ~= P. I heard someone say it's Log(N) but I'm not sure how that could be.

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.

Source Link
CWright
CWright
  • 103
  • 1

Given two identical DOM trees find same node in tree B

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 nodeA in tree A return the current node in treeB.

The complexity for the second approach will be O(N) as 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 P nodes and then down P nodes in treeB and 2P ~= P. I heard someone say it's Log(N) but I'm not sure how that could be.