A problem which is relatively easy to solve is determining
if two trees are equivalent.
Two trees are
*equivalent*
if they both have the same topology
and if the objects contained in corresponding nodes are equal.
Clearly, two empty trees are equivalent.
Consider two non-empty binary trees
and .
Equivalence of trees is given by

A simple, recursive algorithm suffices to test the equivalence of trees.

Since the `BinaryTree` class is ultimately
derived from the `Object` base class,
we must provide a `CompareTo` member function to compare binary trees.
Recall that the compare function is used to compare two objects,
say `obj1` and `obj2` like this:

int result = obj1.CompareTo (obj2);The

So what we need is to define a
*total order*
relation on binary trees.
Fortunately, it is possible to define such a relation for binary trees
provided that the objects contained in the nodes of the trees
are drawn from a totally ordered set.

TheoremConsider two binary trees and and the relation<given by

where is either or and is . The relation

<is a total order.

The proof of Theorem is straightforward albeit tedious. Essentially we need to show the following:

- For any two distinct trees and , such that , either or .
- For any three distinct trees , , and , if and then .

Program gives an implementation of the `CompareTo`
member function for the `BinaryTree` class.
This implementation is based on the total order relation *<* defined
in Theorem .
The `CompareTo` function takes as its lone argument a `const`
reference to an `Object`.
However, normally that object will be another `BinaryTree` instance.
Therefore, the `dynamiccast` on line 4 is normally successful.

**Program:** `BinaryTree` Class `CompareTo` Member Function Definition

The `CompareTo` function compares the two binary trees
`*this` and `arg`.
If they are both empty trees, `CompareTo` returns zero.
If `*this` is empty and `arg` is not,
`CompareTo` returns -1; and
if `arg` is empty and `*this` is not,
it returns 1.

Otherwise, both trees are non-empty.
In this case, `CompareTo` first compares their respective roots.
If the roots are equal, then the left subtrees are compared.
Then, if the roots and the left subtrees are equal,
the right subtrees are compared.

Clearly the worst-case running occurs when comparing identical trees.
Suppose there are exactly *n* nodes in each tree.
Then, the running time of the `CompareTo` function is
,
where is the time needed to compare the objects contained
in the nodes of the trees.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.