Algorithm for finding equal paths in two trees

Question

There are two trees. Each node of the tree contains a value that can be compared with the value from another node of another tree. If the values ​​are equal, then the nodes are equal.

Each node can contain from 0 to an arbitrary number of children.

It is necessary to determine whether it is possible to build equal paths in these two trees? The nodes along these paths must be equal. Both paths should go from the top to the node containing 0 children. The number of nodes along the paths should of course also be equal.

Example:

  a           a        a
 /|\         /|\      / \
b c d       1 d z    x   y
| | |\      | |      |
e f g h     x g      s

The first two trees have equal paths "adg". The third tree has no equal paths with the first two trees.

Is there ready algorithm for solving such a problem? If it exists, then how can it be called, and where can one read about it?

Answer 1

As others have stated, you would need to take the intersection of the given trees, but with the extra condition that the intersecting paths should end in a leaf in both trees.

You could do this by traversing both trees in tandem. This can be a depth-first traversal.

I will assume that node values need not be unique. To avoid that children of one node have to be compared to all children of another, the siblings can be sorted by their value. That way children of two nodes can be compared in linear time. Due to sorting, the whole algorithm runs in O(nlogn). If values are unique in a single tree, then children can be hashed by their values, making the algorithm O(n). But as stated, I will go for the variant where duplicate values are allowed:

Here is an implementation in JavaScript:

class Node {
    constructor(value, ...children) {
        this.value = value;
        // sort the children by their value
        this.children = children.sort();
    }
    
    commonPaths(node) {
        if (this.value !== node.value) return [];
        if (this.children.length + node.children.length == 0) return [this.value];
        let result = [], i = 0, j = 0;
        while (i < this.children.length && j < node.children.length) {
            let a = this.children[i], b = node.children[j];
            for (let path of a.commonPaths(b)) result.push([this.value, ...path]);
            i += (a.value <= b.value); // boolean converts to 0 or 1
            j += (a.value >= b.value);
        }
        return result;
    }
    toString() { return this.value }
}

// Create the trees given in the question
let tree1 = new Node("a",
    new Node("b", new Node("e")),
    new Node("c", new Node("f")),
    new Node("d", new Node("g"), new Node("h"))
);

let tree2 = new Node("a",
    new Node("1", new Node("x")),
    new Node("d", new Node("g")),
    new Node("z")
);

let tree3 = new Node("a", 
    new Node("x", new Node("s")),
    new Node("y")
);

// Get common paths of pairs of these trees
console.log(tree1.commonPaths(tree2));
console.log(tree1.commonPaths(tree3));

Answer 2

The solution involves finding a intersection tree.

To figure out the intersection tree between two trees, we need to intersect the children of each node from both trees.

Suppose you have the trees A and B with roots a and b. Our target is to build an intersection tree C.

If a ≠ b, then C is empty.

Otherwise, let the root c of C be a.

The children of c will be children(a) ∩ children(b).

Now, for each children cᵢ of c, the children of cᵢ will be the intersection of the children of cᵢ in A and in B. Just repeat this until the intersection tree is done.

A good way to represent a tree is as a unordered_map<char, node> and use a unordered_set to represent the children of a node and fast find children in common.

Here is a working example:

#include <bits/stdc++.h>
using namespace std;

/*

  a           a   
 /|\         /|\   
b c d       1 d z  
| | |\      | |      
e f g h     x g     

*/


struct node{
    char value;
    unordered_set<char> children;
    node(){}
    node(char v){value = v; children.clear();}
    void add(char c){children.insert(c);}
};

unordered_map<char, node> A, B, C; //trees

void intersection_tree(char ra){  //method that generates C recursively
    
    auto ita = A.find(ra);
    auto itb = B.find(ra);
    
    if(ita == A.end() || itb == B.end()) return;
    
    node a = ita->second, b = itb->second;
    
    if(a.value == b.value){
        node n(a.value);
        
        vector<char> intersection;
        for (const char& elem: a.children) {
            if(b.children.find(elem) != b.children.end()){
                intersection.push_back(elem);
                n.add(elem);
            }
            C[a.value] = n;
        }
        for(int i = 0; i < intersection.size(); i++){
            intersection_tree(intersection[i]);
        }
    }
}

void dfs(char c, string s = ""){  //dfs to print common paths
    node n = C[c];
    if(n.children.size() == 0) cout<<(s + c)<<endl;
    for (const char& elem: n.children) {
        dfs(elem, s + n.value);        
    }
}


int main(){
    //fill A
    node Aa('a'); Aa.add('b'); Aa.add('c'); Aa.add('d');
    node Ab('b'); Ab.add('e');
    node Ac('c'); Ac.add('f');
    node Ad('d'); Ad.add('g'); Ad.add('h'); 
    node Ae('e'); 
    node Af('f'); 
    node Ag('g'); 
    node Ah('h');
    A['a'] = Aa; A['b'] = Ab; A['c'] = Ac; A['d'] = Ad; A['e'] = Ae; A['f'] = Af; A['g'] = Ag; A['h'] = Ah;
   
    //fill B 
    node Ba('a'); Ba.add('1'); Ba.add('d'); Ba.add('z');
    node B1('1'); B1.add('x');
    node Bd('d'); Bd.add('g');
    node Bz('1');
    node Bx('x');
    node Bg('g');
    B['a'] = Ba; B['1'] = B1; B['d'] = Bd; B['z'] = Bz; B['x'] = Bx; B['g'] = Bg; 
    
    intersection_tree('a');   //generate C
    
    dfs('a');                 //print common paths

    return 0;
}

output: adg

The complexity of this method is O(n).