/usr mark book ch ch ch course cop fall syl spr syl sum syl junk alex junk bill work course cop fall grades prog prog fall prog prog grades figure the (preorderdirectory listing node furthermoreline can be executed at most once for each child of each node but the number of children is exactly one less than the number of nodes finallythe for loop iterates once per execution of line plus once each time the loop ends thusthe total amount of work is constant per node if there are file names to be outputthen the running time is (nanother common method of traversing tree is the postorder traversal in postorder traversalthe work at node is performed after (postits children are evaluated as an examplefigure represents the same directory structure as beforewith the numbers in parentheses representing the number of disk blocks taken up by each file since the directories are themselves filesthey have sizes too suppose we would like to calculate the total number of blocks used by all the files in the tree the most natural way to do this would be to find the number of blocks contained in the subdirectories /usr/mark ( )/usr/alex ( )and /usr/bill ( the total number of blocks is then the total in the