Edit Distance

Edit distance - the minimum number of insertions, deletions and substitutions to change one string/tree into another.

Example for a binary tree:

int tree_edist(tree *t1, tree *t2) {
    if(t1 == NULL) return tree_count(t2); /* insertion */
    if(t2 == NULL) return tree_count(t1); /* deletion */

    /* nodes match, no cost incurred */
    if(t1->key == t2->key) return tree_edist(t1->l, t2->l) + tree_edist(t1->r, t2->r);

    /* substitution */
    return tree_edist(t1->l, t2->l) + tree_edist(t1->r, t2->r) + 1;
};