Exercise 3: Why the Root Is Always First in Pre-Order and Last in Post-Order — Possible Solution ==================================================================== WHY THE ROOT IS ALWAYS FIRST IN PRE-ORDER ------------------------------ Per this chapter's own definition, pre-order visits a node BEFORE any of its children are visited. The traversal always begins by calling the traversal function on the root itself - there is no node "above" the root that could be visited first, since the root is by definition the one node with no parent. The very first action the whole traversal takes, before recursing into anything, is to record the root. Nothing else in the entire tree can ever be recorded before that first action happens, so the root is guaranteed to be first in a pre-order list for ANY rooted tree, regardless of its shape, number of children, or depth. WHY THE ROOT IS ALWAYS LAST IN POST-ORDER ------------------------------ Per this chapter's own definition, post-order visits a node AFTER all of its children (and, recursively, everything beneath them) have already been visited. The root's own children subtrees must be completely finished - every single descendant of the root, however many levels deep - before the root itself can be recorded. Since the root is an ancestor of every other node in the tree (that's what makes it the root), every other node must be recorded before the root is. There is no node left over that could still be recorded after the root, so the root is guaranteed to be last in a post-order list for ANY rooted tree. THE GENERAL PRINCIPLE ------------------------------ Both facts come from the same root cause (no pun intended): the root is defined as having no parent and being an ancestor of every other node. Pre-order's "before children" rule and post-order's "after children" rule, applied to a node with THAT particular relationship to every other node in the tree, mechanically force it to the very front or the very back of the list - this isn't a coincidence specific to any one example tree, it follows directly from what a root is. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation argues from this chapter's own general definitions (what pre-order/post-order visit-timing means, and what makes a node "the root") rather than pointing at a single worked example and generalizing from it, so it holds for any rooted tree rather than only the specific ones already shown in this chapter.