Question

Build a binary search tree for the words oenology, phrenology, campanology, ornithology, ichthyology, limnology, alchemy, and astrology using alphabetical order.

Answer 1

Answer:

The diagram is attached to this response.

Explanation:

In a binary search tree (BST), a node may have a right child and/or a left child which are also nodes, and the following properties hold:

i. the left subtree of a node has nodes whose keys are lesser than that of the given node.

ii. the right subtree of a node has nodes whose keys are greater than that of the given node.

Given words are:

oenology, phrenology, campanology, ornithology, ichthyology, limnology, alchemy, astrology

To build a binary search tree with the given words, do the following:

(i) The first word in the list is the root node of the tree. In this case, the root node is oenology.

(ii) The second word is phrenology. Using alphabetical ordering and relative to the root word (oenology), phrenology tends to be after oenology. Therefore, phrenology is going to be to the right of oenology.

(iii) The third word is campanology. Using alphabetical ordering and relative to the root word (oenology), campanology should be before oenology. Therefore, campanology is going to be to the left of oenology.

(iv) The fourth word is ornithology. Using alphabetical ordering and relative to the root word (oenology), ornithology should be after oenology. Therefore, ornithology is going to be to the right of oenology. Also, since phrenology is already to the right of oenology, ornithology would be to the left of phrenology as alphabetical ordering shows that ornithology is before phrenology. In essence, ornithology would be placed right to oenology but left to phrenology.

(v) The fifth word is ichthyology. Using alphabetical ordering and relative to the root word (oenology), ichthyology should be before oenology. Therefore, ichthyology is going to be to the left of oenology. Also, since campanology is already to the left of oenology, ichthyology would be to the right of campanology as alphabetical ordering shows that ichthyology is after campanology. In essence, ichthyology would be placed left to oenology but right to campanology.

(vi) The sixth word is limnology. Using alphabetical ordering and relative to the root word (oenology), limnology should be before oenology. Therefore, limnology is going to be to the left of oenology. Also, since campanology is already to the left of oenology, limnology would be to the right of campanology as alphabetical ordering shows that limnology is after campanology.  Also, since ichthyology is already to the right of campanology, limnology would be to the right of ichthyology as alphabetical ordering shows that limnology is after ichthyology.  In essence, limnology would be placed left to oenology, right to campanology but right to ichthyology.

(vii) The seventh word is alchemy. Using alphabetical ordering and relative to the root word (oenology), alchemy should be before oenology. Therefore, alchemy is going to be to the left of oenology. Also, since campanology is already to the left of oenology, alchemy would be to the left of campanology as alphabetical ordering shows that alchemy is before campanology. In essence, alchemy would be placed left to oenology but left to campanology.

(viii) The eighth word is astrology. Using alphabetical ordering and relative to the root word (oenology), astrology should be before oenology. Therefore, astrology is going to be to the left of oenology. Also, since campanology is already to the left of oenology, astrology would be to the left of campanology as alphabetical ordering shows that astrology is before campanology.  Also, since alchemy is already to the left of campanology, astrology would be to the right of alchemy as alphabetical ordering shows that astrology is after alchemy.  In essence, astrology would be placed left to oenology, left to campanology but right to alchemy.