Lab $7$: Trees

Lab on Trees

In class you learned that the binary tree data$-$structure could be represented in computer memory contiguously or by random access.

Using whichever representation you are comfortable with, implement a tree. The tree will be inputted into the computer layer$-$by$-$layer starting at the root. The data type of each node will be a String. Input is terminated with $\text{'}-1\text{'}.$

For example:

blue

green

yellow

pink

red

purple

orange

black

brown

$-1$

Which yield the following tree structure:

Tree structure

Question $1.$ Output a pre$-$order traversal of the input tree. $($Output should all be on one line separated by spaces.$)$

e$.$g$.$ output: blue green pink black brown red yellow purple orange

Question $2.$ Output a In$-$order traversal of the input tree.

e$.$g$.$ output: black pink brown green red blue purple yellow orange

Question $3.$ Output a post$-$order traversal of the input tree.

e$.$g$.$ output: black brown pink red green purple orange yellow blue

Hint: The pseudocode for these procedures are given in the slides, you are welcome to use them. Remember only the order of instructions needs to change to answer all three questions above.

DO QUESTION $1,$ QUESTIONN $2$ AND QUESTION$3$