0
\$\begingroup\$

I was asked this as an interview question. I was also asked to assume that there is a function which can compare and say two nodes are identical. I would like to implement that function as well. I'm not sure what's a sure shot way of saying that in pure JavaScript.

    O         O
   / \       / \
  O   O     O   O
     /|\       /|\
    O O O     O O O

Assume two DOM trees with roots: rootA and rootB, the rootB tree being a clone of the rootA tree. Write a function which takes a node in rootA and finds a clone node in the other tree.

I believe there is a better solution than recursion.

jsFiddle

function walkTheDom(root, cb) {
    if (!root) {
        return;
    }
    var r = root;   
    if (cb (r)) {
        foundNode = r;
        return;
    }    
    r = r.firstChild;

    while (r) {
        walkTheDom(r, cb);
        r = r.nextSibling;
    }    

}    

var compare = function (el) {
    //return true if nodes are equal
    //false if they're not
}

function findNode(node, rootB) {
    var foundNode = '';
    walkTheDom(rootB, compare);
    if (foundNode) {
        return foundNode
    }     
}
\$\endgroup\$
  • \$\begingroup\$ compare seems to be missing it's body. Have you made an attempt at writing it or what's it's purpose there? \$\endgroup\$ – Mast Oct 7 '15 at 20:17
  • \$\begingroup\$ I was said that assume compare is provided already, but I prefer to implement that also. Just not sure what's all should be checked to claim two Dom nodes to be equal in pure JavaScript. \$\endgroup\$ – brownmamba Oct 7 '15 at 21:21
1
\$\begingroup\$

It looks like the solution solves the wrong problem: the rootA is completely ignored, as well as the fact that the trees are actually DOM. In a DOM structure it is safe to assume that the node has an access to its parent and siblings. So, given a node in rootA tree, you may trace its path to the root, and then descend the same path down from rootB. Since they are clones, such descend will get you to the node in question. I don't see the need (other than unit test purposes) to compare nodes.

\$\endgroup\$
  • \$\begingroup\$ Well, the solution that I have does a recursive depth first search in rootB tree, which does not require rootA - hence it can be safely ignored. My friend suggested the same solution as you did. And I think its certainly more efficient. Not sure how I'd implement it. I'll probably try my hand at it and see if I can come up with something. Thanks for your solution, but I'm expecting code. \$\endgroup\$ – brownmamba Oct 7 '15 at 19:34
  • \$\begingroup\$ @brownmamba Code in answers isn't mandatory. Answers may be in the form of advice, direction or alternative approach. CodeReview (and even StackOverflow) aren't code-for-free services. \$\endgroup\$ – Joseph Oct 7 '15 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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