# Comparing two finite trees

I need an editor which allows to enter a tree, each node of which may contain several subnodes.

The enter part is easy. I can use just a text editor and a hierarchical list like

``` * a ** b ** c *** d ```

But I also need to compare two trees (find if there are any differences and if there are differences report them).

Order of the nodes does not matter. So the above tree is considered equivalent to

``` * a ** c *** d ** b ```

I'm using Ubuntu Linux, and the software should come with no money paid.

Better than nothing partial answer. This method can return a false positive, (see notes at end), but not a false negative, (i.e. negative results are reliable).

`tsort` is useful util that does topological sorting from standard input. `tsort` requires node paired input, so that this:

``````* a
** b
** c
*** d
``````

Must first be reformatted for `tsort` to look like this:

``````a b
a c
c d
``````

Pipe that through `tsort`:

``````printf '%s %s\n' a b  a c  c d | sort | tsort
``````

Output:

``````a
c
b
d
``````

Using `bash` and `diff`, the two trees in the question can be compared like so:

``````diff <(printf '%s %s\n' a c  c d  a b | sort | tsort) \
<(printf '%s %s\n' a b  a c  c d | sort | tsort)
``````

Output is nothing, since the two trees are equal.

Notes:

• the `tsort` docs need improvement.

• Negative results, (the trees are different), are reliable. Positive results, (the trees are the same), might not be. Some graphs (all trees are graphs) that are different can still have the same sort result. But if `diff` does return something, the trees are absolutely not equal.

Example of false positive, consider the two trees:

``````+---+
| a |
+---+
|
|
v
+---+
| b |
+---+
|
|
v
+---+
| c |
+---+
``````

and:

``````+---+     +---+
| c | <-- | a |
+---+     +---+
|
|
v
+---+
| b |
+---+
``````

Put those trees into `tsort`:

``````paste <(printf '%s %s\n' a b  a c | sort | tsort)  \
<(printf '%s %s\n' a c  c b | sort | tsort)
``````

Output:

``````a       a
c       c
b       b
``````