COMP 250 Lecture Notes - Lecture 21: Call Stack, Local Variable, Root Directory
Document Summary
Often we wish to iterate through or traverse all the nodes of the tree. We generally use the term tree traversal for this. There are two aspects to traversing a tree. One is that we need to follow references from parent to child, or child to its sibling. The second is that we may need to do something at each node. I will use the term visit for the latter. Visiting a node means doing some computation at that node. Depth rst traversal using recursion: pre- and post-order. The rst two traversals that we consider are called depth rst . In these traversals, a node and all its descendents are visited before the next sibling is visited. Rst-traversal of a tree, depending on whether you visit a node before its descendents or after its descendents. In a pre-order traversal, you visit a node, and then visit all its children.