The three traversal algorithms is a recursive algorithm. This means that in order to traverse the entire tree rooted at node A, the algorithm will split and finish the task in three parts:
- traverse the subtree rooted at B (A's left child)
- traverse the subtree rooted rooted at C (A's right child)
- traverse/visit A itself
The order of the three tasks depends on which order you use:
- In-order (Left, Root, Right) does task1, task3, and then task2. - Pre-order (Root, Left, Right) does task3, task1, and then task2. - Post-order (Left, Right, Root) does task1, task2, and then task3
Continue the recursive algorithm: to traverse the subtree rooted at B, it will split the task further and traverse the subtree rooted at B's left child, the subtree rooted at B's right child, and then B.
The "splitting task" continues until the subtree to traverse contains only one root node. In this case, the algorithm visits the root node and returns to the remaining sub-tasks. Same thing happens to the subtree rooted at C, A's right child.
Here are the detailed steps to traverse the tree in the question in 3 different orders and to answer the questions using the traversal results:
- In-order traversal (Left, Root, Right):
- traverse subtree rooted at B
- visit A
- traverse subtree rooted at C
- traverse C's left subtree
- visit C
- traverse C's right subtree
In-order: BADCE
- Pre-order traversal (Root, Left, Right)
- visit A
- traverse subtree rooted at B
- traverse subtree rooted at C
- visit C
- traverse C's left subtree
- traverse C's right subtree
Pre-order: ABCDE
- Post-order traversal (Left, Right, Root)
- traverse subtree rooted at B
- traverse subtree rooted at C
- traverse C's left subtree
- traverse C's right subtree
- visit C
- visit A
Post-order: BDECA
You can check if your traversal results are the same as above.
Looking at the traversal results, we know that the answer to your question 1 is g, and the answer to your question 2 is c.
