DOM tree traversal

Question

I recently interviewed for a frontend engineer position at Facebook. For my phone screen I was the following question: Given a node from a DOM tree find the node in the same position from an identical DOM tree. See diagram below for clarity.

 A         B   O        O  |\       |\  O O      O O   /|\      /|\  O O O    O O O       \        \        O        O 

Here was my solution, I was wondering what I could have done to improve/optimize it.

var rootA, rootB;  function findNodeB(nodeA) {     // Variable to store path up the DOM tree     var travelPath = [];      // Method to travel up the DOM tree and store path to exact node     var establishPath = function(travelNode) {         // If we have reached the top level node we want to return         // otherwise we travel up another level on the tree         if (travelNode === rootA) {             return;         } else {             establishPath(travelNode.parentNode);         }          // We store the index of current child in our path         var index = travelNode.parentNode.childNodes.indexOf(travelNode);         travelPath.push(index);          }      var traverseTree = function(bTreeNode, path) {         if(path.length === 0) {             return bTreeNode;         } else {             traverseTree(bTreeNode.childNodes[path.pop()], path);         }     }      establishPath(rootB, nodeA);      return traverseTree(rootB, travelPath); }            

Answer 1

Since at least Axel showed interest in an iterative solution, here it is:

Given two trees which have identical structure, and a specified node within the first tree, locate the node in the second tree with the same position within the structure.

If we have no other information about the two trees then the position of each node can be characterized as a path from the root node where each step in the path is specified as an index into the childNode array.

function indexOf(arrLike, target) {     return Array.prototype.indexOf.call(arrLike, target); }  // Given a node and a tree, extract the nodes path  function getPath(root, target) {     var current = target;     var path = [];     while(current !== root) {         path.unshift(indexOf(current.parentNode.childNodes, current));         current = current.parentNode;     }     return path; }  // Given a tree and a path, let's locate a node function locateNodeFromPath(root, path) {     var current = root;     for(var i = 0, len = path.length; i < len; i++) {         current = current.childNodes[path[i]];     }     return current; }  function getDoppleganger(rootA, rootB, target) {     return locateNodeFromPath(rootB, getPath(rootA, target)); } 

EDIT: As Blue Skies observed, childNodes doesn't have .indexOf(). Updating with Array.prototype.indexOf.call()