TAOCP 6.2.2 Exercise 1
Let $A$ denote the null pointer used in Algorithm T.
Section 6.2.2: Binary Tree Searching
Exercise 1. [15] [15] Algorithm T has been stated only for nonempty trees. What changes should be made so that it works properly for the empty tree too?
Verified: no
Solve time: 1m19s
Solution
Let $A$ denote the null pointer used in Algorithm T.
An empty binary search tree is represented by setting $\mathrm{ROOT} = A$.
Algorithm T begins by setting $P \leftarrow \mathrm{ROOT}$. In the empty case this gives $P \leftarrow A$. The step that follows must therefore be able to handle $P = A$.
Modify the initial part of Algorithm T so that step T1 reads in full:
T1. [Empty tree or node found.] If $P = A$, terminate the search unsuccessfully.
No further modification of the comparison and link-following steps is required, since every recursive descent eventually reaches a null link, and the same condition $P = A$ applies uniformly.
This change makes the empty tree case consistent with the general termination condition already used for unsuccessful search in the nonempty case, while ensuring that initialization with $\mathrm{ROOT} = A$ is valid input. ∎