Is there a way to find a path in a tree?

Question

Let's say we have a tree like the one below. Is there an algorithm that given 2 nodes find the path that connects them. For example, given (A,E) it will return [A,B,E], or given (D,G) it will return [D,B,A,C,G]

           A
         /   \
       B       C
      / \     / \
     D   E   F   G

Yes. Can be implemented in `O(N)` easily. Recursively check if parent node joins the two nodes. — theWiseBro, Apr 29 '20 at 09:07
Similar to: https://stackoverflow.com/questions/713508/find-the-paths-between-two-given-nodes — Rishabh, Apr 29 '20 at 23:35

score 0 · Accepted Answer · answered Apr 29 '20 at 21:52

You will need to have a tree implementation where a child node has a link to its parent.

Then for both nodes you can build the path from the node to the root, just by following the parent link.

Then compare the two paths, starting from the ends of the paths (where the root is): as long as they are the same, remove that common node from both paths.

Finally you are left with two diverting paths. Reverse the second, and join the two paths, putting the last removed node in between the two.

Here is an implementation in JavaScript:

function getPathToRoot(a) {
    if (a.parent == null) return [a];
    return [a].concat(getPathToRoot(a.parent));
}

function findPath(a, b) {
    let p = getPathToRoot(a);
    let q = getPathToRoot(b);
    let common = null;
    while (p.length > 0 && q.length > 0 && p[p.length-1] == q[q.length-1]) {
        common = p.pop();
        q.pop();
    }
    return p.concat(common, q.reverse());
}

// Create the example tree
let nodes = {};
for (let label of "ABCDEFG") {
    nodes[label] = { label: label, parent: null };
}
nodes.B.parent = nodes.C.parent = nodes.A;
nodes.D.parent = nodes.E.parent = nodes.B;
nodes.F.parent = nodes.G.parent = nodes.C;

// Perform the algorithm
let path = findPath(nodes.E, nodes.G);

// Output the result
console.log("Path from E to G is:");
for (let node of path) {
    console.log(node.label);
}

Is there a way to find a path in a tree?

1 Answers1