TAOCP 2.3.1 Exercise 28
Algorithm `C` constructs a new tree by creating a new node corresponding to each node of the original tree, copying the information field, and preserving the left and right subtree relationships.
Section 2.3.1: Traversing Binary Trees
Exercise 28. [00] After Algorithm C has been used to make a copy of a tree, is the new binary tree equivalent to the original, or similar to it?
Verified: no
Solve time: 47s
Algorithm C constructs a new tree by creating a new node corresponding to each node of the original tree, copying the information field, and preserving the left and right subtree relationships. Hence there is a one-to-one correspondence between the nodes of the original tree and the nodes of the copy that preserves both structure and information.
Therefore the copied tree is equivalent to the original tree. Since equivalent trees are, in particular, similar, the copy is also similar; however, equivalence is the stronger statement and is the appropriate answer.
$$ \boxed{\text{The new binary tree is equivalent to the original tree, hence also similar to it.}} $$