The following tree is a binary search tree on college majors

The following tree is a binary search tree on college majors, using alphabetic order to build the tree:

(a) Write down the order that each major must have been added to the binary search tree in order to produce the tree shown. (Multiple correct possibilities. Multiple incorrect possiblities.)

(b) Show an in-order traversal of the tree.

Solution

a) Insertions in alphabetical order.

1. computer engineering

computer engineering

2. computer science (e<s) insert in left subtree

computer science

/

computer engineering

3. crop science (r>o) insert in right subtree

computer science

/ \\

computer engineering crop science

4. english literature(e>c) insert it into right subtree of crop science

computer science

/ \\

computer engineering crop science

\\

english literature

5. french(french >crop science but crop science already has right child. so make it parent of crop science . As french > computer science so make it parent of computer science)

french

/

computer science

/ \\

computer engineering crop science

\\

english literature

6. geology(geology > french) so make it parent as right subtree is already there.

geology

/

french

/

computer science

/ \\

computer engineering crop science

\\

english literature

7. history(make it right child of geology as h>g)

geology

/ \\

french history

/

computer science

/ \\

computer engineering crop science

\\

english literature

8. mathematics(m>h so make mathematics parent of history and history left child of mathematics)

geology

/ \\

french mathematics

/ /

computer science history

/ \\

computer engineering crop science

\\

english literature

b) Inorder traversal of tree

computer engineering

computer science

crop science

english literature

french

geology

history

mathematics