title: Find corresponding node in an identical DOM tree - what is the average and worse time complexity?
body: <p><a href="https://stackoverflow.com/questions/19779438/dom-tree-traversal">Here is the question</a> posted on here years ago about an interview question where given a node from a DOM tree, we need to find the node in the same position from an identical DOM tree.</p>
  <p>Here is the an iterative solution I came up with</p>
  <pre class="lang-js prettyprint-override"><code>const findCorrespondingNode = (rootA, rootB, nodeA) =&gt; {
    let currentNode = nodeA;
    const path = [];
    while (currentNode !== rootA) {
      const index = Array.prototype.indexOf.call(
        currentNode.parentElement.children,
        currentNode
      );
      path.push(index);
      currentNode = currentNode.parentElement;
    }
    currentNode = rootB;
    while (path.length) {
      currentNode = currentNode.children[path.pop()];
    }
  
    return currentNode;
  }
  </code></pre>
  <p>Basically I just walk backwards from the target to root, creating the reverse path. The reverse path is an array where each element is the child index of a node.
  Travel down the path from rootB to target, popping off the next index until the path array is empty. Finally we return the pointer to the target node.</p>
  <p>My question is:</p>
  <ol>
  <li>what is the (average) time complexity for this solution? The worse case is easy since we need to visit each node once so it is going to be <code>O(n)</code>, <code>n</code> being the number of DOM nodes in the DOM tree. I think it happens when we have two linked lists and the target node is the last node in each linked list. <strong>The confusion part for me is that</strong> for each level we are also calling <code>Array.prototype.indexOf</code> to get the index, and this might take up to <code>O(D)</code>, D being the tree's diameter and for a leaf node it is going to take <code>O((some-constant)n)</code> to get the index. <strong>, More importantly,</strong> what is the <strong>average</strong> time complexity? We are traversing a tree twice. It seems like it is going to be the height or the depth of the tree. If it is a completely balanced tree, the height of the tree is going to be <code>logN</code>. Does that mean the average time complexity is <code>logN</code>?</li>
  <li>If I write the solution using a recursive DFS approach, where we traverse both trees simultaneously, i.e.</li>
  </ol>
  <pre class="lang-js prettyprint-override"><code>const findCorrespondingNode = (rootA, rootB, target) =&gt; {
    if(rootA === target) {
      return rootB;
    }
    for (let i = 0; i &lt; rootA.children.length; i++) {
      const foundNode = findCorrespondingNode(rootA.children[i], rootB.children[i], target);
      if(foundNode) return foundNode;
    }
  }
  </code></pre>
  <p>What is the time complexity in this case? Still worse case <code>O(n)</code> and average/best case <code>O(logN)</code>. Is this recursive approach better than the iterative approach in terms of time complexity since we wouldn't need to do <code>indexOf</code> for each level?</p>