CODEWITHSUNDEEP
javascriptdom
thedjpetersen
thedjpetersen

Reputation: 29295

DOM tree traversal

I recently interviewed for a frontend engineer position. 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);
}

Upvotes: 31

Views: 11450

Answers (4)

Yuriy Kvartsyanyy
Yuriy Kvartsyanyy

Reputation: 2886

Here is parallel traversing solution

function findDomNodeInTree(rootA, rootB, targetNode) {
    if (rootA === targetNode){
        return rootB;
    }

    let nodeB = null;

    for (let i=0; i<rootA.childNodes.length && nodeB === null; i++){
        nodeB = findDomNodeInTree(rootA.childNodes[i], rootB.childNodes[i], targetNode);
    }

    return nodeB;
}

It's time complexity is O(N) and in worst case we need to traverse entire tree.

I don't think it less efficient than solution with finding path first. At each level there is a call to indexOf which may need to traverse all nodes on that level to find the index.

Upvotes: 7

amilajack
amilajack

Reputation: 127

Instead of Array.prototype.indexOf.call, you can use Array.from (standardized in ES6):

Array.from(travelNode.parentNode.childNodes).indexOf(travelNode);

Upvotes: 3

kennytilton
kennytilton

Reputation: 1064

I would traverse the two trees in parallel and when I got to the node in treeA return the parallel node.

Upvotes: 0

Mike Edwards
Mike Edwards

Reputation: 3771

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()

Upvotes: 23

Related Questions