<p>Tree Edit Distance is a generalization of string edit distance. The distance between two trees is the minimum number of node insertions \ deletions \ and relabels required to turn one tree into the other. (when we delete node v, v's children become children of parent(v)).
The problem is NP-hard when the trees are unordered, but when they are ordered (i.e., there is a left-to-right order among siblings) the problem is solvable in O(n^3) time (as in the paper that Sadeq mentioned). A good survey that describes this: <a href="http://portal.acm.org/citation.cfm?id=1085283">http://portal.acm.org/citation.cfm?id=1085283</a></p>

CC BY-SA 2.5
2011-02-07T12:49:42.717Z
Thanks Aviv. It will be great if you merge your responses (I think you have issues using your previous account). You can use the advices in [this post](http://meta.cstheory.stackexchange.com/q/268/873) (Specially, [this link](http://cstheory.stackexchange.com/users/account-recovery)).
Sadeq Dousti
CC BY-SA 4.0
2019-01-12T03:58:44.657Z
How would this approach cover different trees with eqivalent polynomials
Narek Bojikian
CC BY-SA 2.5
2011-02-07T11:22:48.290Z
2011-02-07T11:22:48.290Z
Aviv
<p>A colleague who works on <strong>genetic programming</strong> asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy algorithm. So, I thought it's worth mentioning here.</p>

<hr>

<p>Consider two polynomials which are represented by their expression trees. For instance, <span class="math-container">$x^3-2x+1$</span> and <span class="math-container">$x^2 + 4$</span> are illustrated below:</p>

<p><a href="https://i.sstatic.net/GNwbs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GNwbs.png" alt=""></a></p>

<p>Rules:</p>

<ol>
<li>Each node is either a <strong>variable name</strong> (<span class="math-container">$x, y, z, \ldots$</span>), a <strong>number</strong>, or an <strong>operation</strong> (+,-,×).</li>
<li>The in-order traversal of the tree should result in a valid polynomial.</li>
<li>Operation nodes have in-degree 2. Other nodes have in-degree 0. All nodes have out-degree 1 (except root, whose out-degree is 0).</li>
</ol>

<p>On a node N of the tree, define the <strong>basic operation</strong> as follows:</p>

<ol>
<li>A basic operation can change the label of the node. For instance, <span class="math-container">$x$</span> can be changed to 3, or + can be changed to <span class="math-container">$\times$</span>. </li>
<li>A basic operation can build an expression tree on top of N (see the example below).</li>
</ol>

<p>The cost of the basic operation of <strong>type 1</strong> is 1. The cost for <strong>type 2</strong> is equal to the number of {+,-,×} operations in the newly built expression tree.</p>

<p><strong>Example for type 2:</strong> The cost of the following basic operation is 2, since the expression tree built on top of node N uses two operations (- and ×).</p>

<p><a href="https://i.sstatic.net/UHb1F.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/UHb1F.png" alt=""></a></p>

<p>Let T1 and T2 be two expression trees representing polynomials.
Define the <em>distance</em> of T1 and T2 as follows: the minimum cost of basic operations for converting T1 to T2. Note that we don't require the converted tree to have the same structure as T2. We just want it to compute the same polynomial as T2. (See the comments for an example.)</p>

<blockquote>
  <p><strong>The problem:</strong> Given T1 and T2, present an algorithm which computes their distance.</p>
</blockquote>

<p><strong>Example 1:</strong> Let T1 and T2 are the two trees illustrated at the beginning of this post. To convert the right tree to the left tree, one can build a tree of cost 3 on top of ×, and change 4 to 1 (the total cost is 4).</p>

<p><strong>Example 2:</strong> Let T1=<span class="math-container">$x^4$</span> be represented by the following tree. To convert T1 to T2=<span class="math-container">$x^4+4x^3+6x^2+4x+1$</span>, it suffices to add 1 to each of the <span class="math-container">$x$</span> nodes, to optain <span class="math-container">$(x+1)^4$</span>=T2. This can be done by adding a cost-1 expression tree on top of each <span class="math-container">$x$</span> node. This example shows that the term-by-term conversion (which I called the <strong>greedy approach</strong> at the beginning of this post) is not an optimal approach. That is, if one wants to produce terms in T2 which are not present in T1 (i.e. <span class="math-container">$4x^3$</span>, <span class="math-container">$6x^2$</span>, <span class="math-container">$4x$</span>, and 1), the cost will be much higher.</p>

<p><a href="https://i.sstatic.net/xXPuz.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xXPuz.png" alt=""></a></p>

CC BY-SA 4.0
2018-05-07T02:13:54.720Z
Anyone reading this who just wants to import a library should have a look at [APTED](https://github.com/DatabaseGroup/apted). Open source Java, MIT licence, reasonable fast. Most other languages have ways of integrating with Java.
AnnanFay
CC BY-SA 2.5
2011-02-06T11:43:49.473Z
If "delete" operation is not allowed, then the distance is not a distance. For example: a tree T1=(x*x)+4 cannot be transformed to T2=x, but T2 can be transformed to T1 adding (*x) and then (+4) on top of x. Is it ok ? Or you should define the distance as the minum operations required to convert T1 to T2 or T2 to T1.
Marzio De Biasi
CC BY-SA 2.5
2011-02-06T12:09:10.593Z
Very well posed question, might serve as an example in our FAQ. Any particular reason why nodes can not be expanded, say $x \mapsto \times(x, x)$, or reduced, say $x \mapsto \times(x, x)$?
Raphael
CC BY-SA 2.5
2011-02-06T12:12:49.120Z
@Vor: In the example you provided ($x \times x + 4$), the relabeling works: change the label of one of the $x$ nodes to 1. You obtain $1 \times x + 4 = x + 4$. Then change the label of 4 to 0, you obtain: $x$. Correct?
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T12:15:36.483Z
@Raphael: Thanks for your opinion about the question :) I didn't understand the difference between expansion and reduction, because the examples you provided were identical: $x \mapsto \times(x, x)$. I think it's a typo, right?
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T12:37:40.127Z
Indeed, I intended to turn it around. :> As for $1 \times x + 4 = x + 4$, this is algebraically clear, but you have indeed no operation that transforms from left to right. Or do we not need to have *the same* tree at the end, but only an *equivalent* one?
Raphael
CC BY-SA 2.5
2011-02-06T14:21:13.403Z
@Raphael: You're right. I should have mentioned that we only require the trees to be **equivalent**. I'll correct this in the body of the question.
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T14:23:33.370Z
The second example doesn't seem to be the same as the problem statement: are the inputs trees or polynomials?
Peter Taylor
CC BY-SA 2.5
2011-02-06T14:26:26.953Z
@Peter: The inputs are polynomials, but they are represented as trees. I'll change the subject of this post to clarify it. (Also, note the problem statement: Given T1 and T2,...)
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T14:30:24.840Z
@Sadeq, my point was that the problem statement talks about trees, the first example has two trees as input, but the second example appears to have one tree and one polynomial as input.
Peter Taylor
CC BY-SA 2.5
2011-02-06T14:56:49.510Z
@Peter: You're totally right. It seems that I was too lazy to draw the polynomial for $x^4+4x^3+6x^2+4x+1$. Just try to consider the most natural case, since it will occupy a lot of the page if I try to illustrate it. In [Polish notation](http://en.wikipedia.org/wiki/Polish_notation), it will be $+(+(+(+(\times(\times(x,x),\times(x,x)),\times(4,\times(x,\times(x,x)))),\times(6,\times(x,x))),\times(4,x)),1)$.
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T15:57:00.737Z
Have you considered using a "Tree Edit Distance" algorithm?
Aviv
CC BY-SA 2.5
2011-02-06T16:47:53.730Z
Do you mean [this algorithm](http://www.wisdom.weizmann.ac.il/~oweimann/TED/TED.html)?
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T17:06:26.870Z
Can't really answer, but +1 for the gorgeous diagramming (also, the nice question ;)
Agos
CC BY-SA 2.5
2011-02-06T17:59:24.063Z
If I am not mistaken, even deciding whether the cost is 0 or not is not known to be in deterministic polynomial time (but is known to be in randomized polynomial time).
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T19:05:01.930Z
@Tsuyoshi: Could you please elaborate?
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T19:06:59.700Z
The cost is equal to 0 if and only if the two given (division-free) arithmetic formulas represent the same polynomial.  If I remember it correctly, this is a typical problem in coRP (by random assignment) which is not known to be in P.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T19:56:41.723Z
@Tsuyoshi: Oh, I see. You're pointing at the **polynomial identity testing** problem. (Good references: [[1](http://cstheory.stackexchange.com/q/1772/873)] and [[2](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)]). I must think about this. Meanwhile, any suggestion is welcome.
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T20:08:17.640Z
Yes, that’s it.  It seems that in the _typical_ version of the polynomial identity testing problem, two input polynomials are given as circuits, not formulas.  So my wording that the formula version is “typical” was probably inaccurate.  Anyway putting even the formula version in P seems to be an open problem.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T20:57:18.237Z
@Tsuyoshi: I have yet to talk to my colleague about this issue, but I think it'll be no problem: We can still compare the polynomial trees in poly-time with enough accuracy, and that's enough for the genetic programming (I *guess*).
Sadeq Dousti
CC BY-SA 2.5
2011-02-06T21:04:35.200Z
Well, my point is that we cannot hope for a deterministic polynomial-time exact algorithm for the problem.  I do not rule out the possibility that there may be a randomized algorithm or a deterministic approximate algorithm (with respect to a suitable approximation measure), but to find them, we have to be aware that we need something _other than_ the most basic kind of algorithm, that is, a deterministic poly-time exact algorithm.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T21:44:50.530Z
@Sadeq in your question you talk about "trees" (T1, T2) so I thought that both T1 and T2 were fixed, in this case x+0 != x (they are different trees, even if they represent the same polynomial). However I see that the focus is on the polynomial identity testing problem.
Marzio De Biasi
CC BY-SA 2.5
2011-02-07T01:16:35.023Z
In fact, we have problems just figuring out wether or not we can terminate (i.e. wether what we have is equivalent tot he target), let alone figure out good steps.
Raphael
CC BY-SA 2.5
2011-02-07T02:08:59.117Z
@Vor: In the current formulation, the input T1 is really a tree and the input T2 is a polynomial which just happens to be given as a tree, in the following sense.  Changing T1 to a different tree which represents the same polynomial can change the answer in general, whereas changing T2 in a similar way does not.
Tsuyoshi Ito
<ds.algorithms><tree><ai.artificial-intel><genetic-programming>
Finding the distance between two polynomials (represented as trees)
Sadeq Dousti
# Finding the distance between two polynomials (represented as trees)

(Asked by: username_0 on 2011-02-06)

A colleague who works on **genetic programming** asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy algorithm. So, I thought it's worth mentioning here.

---

Consider two polynomials which are represented by their expression trees. For instance, $x^3-2x+1$ and $x^2 + 4$ are illustrated below:

[![](https://i.sstatic.net/GNwbs.png)](https://i.sstatic.net/GNwbs.png)

Rules:

1. Each node is either a **variable name** ($x, y, z, \ldots$), a **number**, or an **operation** (+,-,×).
2. The in-order traversal of the tree should result in a valid polynomial.
3. Operation nodes have in-degree 2. Other nodes have in-degree 0. All nodes have out-degree 1 (except root, whose out-degree is 0).

On a node N of the tree, define the **basic operation** as follows:

1. A basic operation can change the label of the node. For instance, $x$ can be changed to 3, or + can be changed to $\times$.
2. A basic operation can build an expression tree on top of N (see the example below).

The cost of the basic operation of **type 1** is 1. The cost for **type 2** is equal to the number of {+,-,×} operations in the newly built expression tree.

**Example for type 2:** The cost of the following basic operation is 2, since the expression tree built on top of node N uses two operations (- and ×).

[![](https://i.sstatic.net/UHb1F.png)](https://i.sstatic.net/UHb1F.png)

Let T1 and T2 be two expression trees representing polynomials.
Define the *distance* of T1 and T2 as follows: the minimum cost of basic operations for converting T1 to T2. Note that we don't require the converted tree to have the same structure as T2. We just want it to compute the same polynomial as T2. (See the comments for an example.)

> **The problem:** Given T1 and T2, present an algorithm which computes their distance.

**Example 1:** Let T1 and T2 are the two trees illustrated at the beginning of this post. To convert the right tree to the left tree, one can build a tree of cost 3 on top of ×, and change 4 to 1 (the total cost is 4).

**Example 2:** Let T1=$x^4$ be represented by the following tree. To convert T1 to T2=$x^4+4x^3+6x^2+4x+1$, it suffices to add 1 to each of the $x$ nodes, to optain $(x+1)^4$=T2. This can be done by adding a cost-1 expression tree on top of each $x$ node. This example shows that the term-by-term conversion (which I called the **greedy approach** at the beginning of this post) is not an optimal approach. That is, if one wants to produce terms in T2 which are not present in T1 (i.e. $4x^3$, $6x^2$, $4x$, and 1), the cost will be much higher.

[![](https://i.sstatic.net/xXPuz.png)](https://i.sstatic.net/xXPuz.png)

**Tags:** ds.algorithms, tree, ai.artificial-intel, genetic-programming
> **Comments:**
> **username_2**: If "delete" operation is not allowed, then the distance is not a distance. For example: a tree T1=(x*x)+4 cannot be transformed to T2=x, but T2 can be transformed to T1 adding (*x) and then (+4) on top of x. Is it ok ? Or you should define the distance as the minum operations required to convert T1 to T2 or T2 to T1.  
> **username_3**: Very well posed question, might serve as an example in our FAQ. Any particular reason why nodes can not be expanded, say $x \mapsto \times(x, x)$, or reduced, say $x \mapsto \times(x, x)$?  
> **username_0**: @Vor: In the example you provided ($x \times x + 4$), the relabeling works: change the label of one of the $x$ nodes to 1. You obtain $1 \times x + 4 = x + 4$. Then change the label of 4 to 0, you obtain: $x$. Correct?  
> **username_0**: @Raphael: Thanks for your opinion about the question :) I didn't understand the difference between expansion and reduction, because the examples you provided were identical: $x \mapsto \times(x, x)$. I think it's a typo, right?  
> **username_3**: Indeed, I intended to turn it around. :> As for $1 \times x + 4 = x + 4$, this is algebraically clear, but you have indeed no operation that transforms from left to right. Or do we not need to have *the same* tree at the end, but only an *equivalent* one?  
> **username_0**: @Raphael: You're right. I should have mentioned that we only require the trees to be **equivalent**. I'll correct this in the body of the question.  
> **username_4**: The second example doesn't seem to be the same as the problem statement: are the inputs trees or polynomials?  
> **username_0**: @Peter: The inputs are polynomials, but they are represented as trees. I'll change the subject of this post to clarify it. (Also, note the problem statement: Given T1 and T2,...)  
> **username_4**: @Sadeq, my point was that the problem statement talks about trees, the first example has two trees as input, but the second example appears to have one tree and one polynomial as input.  
> **username_0**: @Peter: You're totally right. It seems that I was too lazy to draw the polynomial for $x^4+4x^3+6x^2+4x+1$. Just try to consider the most natural case, since it will occupy a lot of the page if I try to illustrate it. In [Polish notation](http://en.wikipedia.org/wiki/Polish_notation), it will be $+(+(+(+(\times(\times(x,x),\times(x,x)),\times(4,\times(x,\times(x,x)))),\times(6,\times(x,x))),\times(4,x)),1)$.  
> **username_5**: Have you considered using a "Tree Edit Distance" algorithm?  
> **username_0**: Do you mean [this algorithm](http://www.wisdom.weizmann.ac.il/~oweimann/TED/TED.html)?  
> **username_6**: Can't really answer, but +1 for the gorgeous diagramming (also, the nice question ;)  
> **username_7**: If I am not mistaken, even deciding whether the cost is 0 or not is not known to be in deterministic polynomial time (but is known to be in randomized polynomial time).  
> **username_0**: @Tsuyoshi: Could you please elaborate?  
> **username_7**: The cost is equal to 0 if and only if the two given (division-free) arithmetic formulas represent the same polynomial.  If I remember it correctly, this is a typical problem in coRP (by random assignment) which is not known to be in P.  
> **username_0**: @Tsuyoshi: Oh, I see. You're pointing at the **polynomial identity testing** problem. (Good references: [[1](http://cstheory.stackexchange.com/q/1772/873)] and [[2](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)]). I must think about this. Meanwhile, any suggestion is welcome.  
> **username_7**: Yes, that’s it.  It seems that in the _typical_ version of the polynomial identity testing problem, two input polynomials are given as circuits, not formulas.  So my wording that the formula version is “typical” was probably inaccurate.  Anyway putting even the formula version in P seems to be an open problem.  
> **username_0**: @Tsuyoshi: I have yet to talk to my colleague about this issue, but I think it'll be no problem: We can still compare the polynomial trees in poly-time with enough accuracy, and that's enough for the genetic programming (I *guess*).  
> **username_7**: Well, my point is that we cannot hope for a deterministic polynomial-time exact algorithm for the problem.  I do not rule out the possibility that there may be a randomized algorithm or a deterministic approximate algorithm (with respect to a suitable approximation measure), but to find them, we have to be aware that we need something _other than_ the most basic kind of algorithm, that is, a deterministic poly-time exact algorithm.  
> **username_2**: @Sadeq in your question you talk about "trees" (T1, T2) so I thought that both T1 and T2 were fixed, in this case x+0 != x (they are different trees, even if they represent the same polynomial). However I see that the focus is on the polynomial identity testing problem.  
> **username_3**: In fact, we have problems just figuring out wether or not we can terminate (i.e. wether what we have is equivalent tot he target), let alone figure out good steps.  
> **username_7**: @Vor: In the current formulation, the input T1 is really a tree and the input T2 is a polynomial which just happens to be given as a tree, in the following sense.  Changing T1 to a different tree which represents the same polynomial can change the answer in general, whereas changing T2 in a similar way does not.  
> **username_1**: Anyone reading this who just wants to import a library should have a look at [APTED](https://github.com/DatabaseGroup/apted). Open source Java, MIT licence, reasonable fast. Most other languages have ways of integrating with Java.  

---

## 1 answers

### Answer by username_5 on 2011-02-07. Score: 10 | Accepted answer

Tree Edit Distance is a generalization of string edit distance. The distance between two trees is the minimum number of node insertions \ deletions \ and relabels required to turn one tree into the other. (when we delete node v, v's children become children of parent(v)).
The problem is NP-hard when the trees are unordered, but when they are ordered (i.e., there is a left-to-right order among siblings) the problem is solvable in O(n^3) time (as in the paper that Sadeq mentioned). A good survey that describes this: <http://portal.acm.org/citation.cfm?id=1085283>

> **Comments:**
> **username_0**: Thanks Aviv. It will be great if you merge your responses (I think you have issues using your previous account). You can use the advices in [this post](http://meta.cstheory.stackexchange.com/q/268/873) (Specially, [this link](http://cstheory.stackexchange.com/users/account-recovery)).  
> **username_8**: How would this approach cover different trees with eqivalent polynomials  

---

