"and traverse it in its entirety. 3. Do the same with the right child. It’s tricky because you have to remember that each time you “treat a child as a subtree” you do the whole traversal process on that subtree. This involves remembering where you were once you finish. Follow this example carefully. For the tree in Figure 5.17, we be- gin by visiting G. Then, we traverse the whole “K subtree.” This involves visiting K itself, and then traversing its whole left subtree (anchored at D). After we visit the D node, we discover that it actually has no left subtree, so we go ahead and traverse its right subtree. This visits O followed by I (since O has no left subtree either) which finally returns back up the ladder. It’s at this point where it’s easy to get lost. We finish visiting I, and then we have to ask “okay, where the heck were we? How did we get here?” The answer is that we had just been at the K node, where we had traversed its left (D) subtree. So now what is it time to do? Traverse the right subtree, of course, which is M. This involves visiting M, C, and E (in that order) before returning\n\n116 CHAPTER 5. STRUCTURES to the very top, G. Now we’re in the same sort of situation where we could have gotten lost before: we’ve spent a lot of time in the tangled mess of G’s left subtree, and we just have to remember that it’s now time to do G’s right subtree. Follow this same procedure, and the entire order of visitation ends up being: G, K, D, O, I, M, C, E, H, A, B, F, N, L. (See Figure 5.18 for a visual.) G 1 K 2 D 3 O 4 I 5 M 6 C 7 E 8 H 9 A 10 B 11 F 12 N 13 L 14 Figure 5.18: The order of node visitation in pre-order traversal."