We help IT Professionals succeed at work.

How does this pseudocode for Tree traversals work?

shampouya
shampouya asked
on
My algorithms textbook has a pseudocode implementation of how to list the names of all the files in a tree directory. Let's say you have this tree directory right here. Does the pseudocode below know to print the names of the three files in the first child folder and then print the three items in the second folder, or does the code have to be called once for each path?

ParentFolder
ChildFolder1  -  ChildFolder2
file1,file2,file3  -  file4,file5,file6
private void listAll( int depth )
{
	printName( depth ); // Print the name of the object
		if( isDirectory( ) )
 			for each file c in this directory (for each child)
				c.listAll( depth + 1 );


public void listAll( )
{
	listAll( 0 );
}

Open in new window

Comment
Watch Question

BRONZE EXPERT

Commented:
This is a recusive algorithm. Note that the function calls itself inside it. Assuming the print with depth prints the object name, functions calls itself over and over until it reaches a leaf node which is a file or directory with no directory in it
BRONZE EXPERT

Commented:
In short no, it will print everything without any more calls
BRONZE EXPERT

Commented:
You know every recursive routine has a clear visible stopping criteria.  This is where it should back track and return back to the function that called it.  Here you have implicit criteria which is when the object not a directory.  It is only calling itself when the current object is a directory.  If the sub directory has another directory, then the function again calls itself for each of the sub directory and so on.

Author

Commented:
Oh ok, I think I see it now. When you said back track I was wondering how it back tracks. Usually when I think of "back track" I think of nested loops. But this program does have nested loops in a sense, because the recursion in line 6 takes place within a loop, and then it invokes a method that contains a loop. Am I visualizing it correctly?
BRONZE EXPERT

Commented:
Back tracking here would mean the following:

For the sake of simplicity suppose we have the following structure.  Capitals (upper case) is directory, lowercase for file.

A->B->C->D->e

listAll(0) is called.  -- instance 1 of listAll
prints A
calls itself for B
listAll(1)                -- instance 2 of listAll
again there is only one directory
prints B
there is a directory C
listAll(2) is called   -- instance 3 of listAll
prints C
there is only one directory no file
listAll(3) is called  -- instance 4 of listAll
prints D
then there is an object, e
print e
there is no directory so it cannot enter the if part

BACK TRACKING
listAll(3) function returns to listAll(2) which had called it.

It has no more objects and nothing more to do so it back tracks again.  
Function returns to the calling function listAll(1)

It has nothing more to do

It returns to calling function listAll(0)
It just returns.

Author

Commented:
I think you explain "it just returns" in terms of "there is nothing left to do", but that doesn't explain what exactly it returns to. It helps when I visualize it as if it were a case of nested for loops. For example, in this code right here the inner loop prints 10 stars and then back tracks to the outer loop once it is done, and a new row begins. I know this isn't exactly what is happening in the recursive algorithm, but the "baton" is being passed back in the same way to the outer loop on line 5. Am I making sense?

for(i = 0, i < 10, i++){
     for(k = 0, k < 10, k++)
          System.out.print("*");
     System.out.println("");
}
BRONZE EXPERT
Commented:
It returns to the first listAll in line 9.

Yes, you can think this way although in this case no functions are being called and when it back tracks, it doesn't return back to a calling function, just to the outer loop.

Author

Commented:
thanks

Explore More ContentExplore courses, solutions, and other research materials related to this topic.