Comparing Trees

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Comparing Trees

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 CompareTo function returns a negative number if

; a positive number if

; and zero if

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.

Theorem Consider 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 .

The details of the proof are left as an exercise for the reader (Exercise

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.

program17339
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.