Popular posts

Hey Rajat, great post! The explanation and the image really helped to understand it.

I solved using your initial solution, but slightly differently:

function getPath(node, rootA) {
    const path = [];
    let currentNode = node;

    while (currentNode !== rootA) {
        const parent = currentNode.parentElement;
        const index = [...parent.children].indexOf(currentNode);
        path.unshift(index);
        currentNode = parent;
    }

    return path;
}

function getNodeFromPath(rootB, path) {
    return path.reduce((node, index) => node.children[index], rootB);
}

I got the path in the top-down order, that's why I used unshift instead of push, and then I reduced that path until its last item to find the correspondent node from root B.

Now, doing this recursively would be:

function findNode(nodeA, nodeB, targetNode) {
    for (let index = 0; index < nodeA.childElementCount; index++) {
        const currentNode = nodeA.children[index];

        if (currentNode === targetNode) {
            return nodeB.children[index];
        }

        if (currentNode.childElementCount) {
            return findNode(currentNode, nodeB.children[index], targetNode);
        }
    }
}

The idea is to go from the top until finding the node from root A. Once that is done, return the node from root B at the same position, otherwise, loop its children (if any) using the same function (recursively).

The recursive solution is probably more performant because:

• it loops through the tree once, while the interactive solution has to go twice. First to find the path, then to find the node from the path itself
• it doesn't create new arrays like the interactive one does, to get the path and also to find the index of the node from the children when getting the path

I'm not sure how to express that complexity in terms of the Big O notation, my guess is that the recursive solution is O(n) where n is the length of root A's tree. Maybe the interactive solution would be expressed in the same way, although we are looping it twice. Any ideas?