Authors:

Linda Null ,julia Lobur

Chapter:

Data Structures And The Computer

Exercise:

Exercises

Question:9 | ISBN:9780763704445 | Edition: 3

**9.
**Most books concerning algorithms and data structures present
traversal algorithms as recursive procedures. (Recursive procedures
are subroutines or functions that call themselves.) However, the
*computer *achieves this recursion using iteration! The
algorithm below uses a stack to perform an iterative preorder
traversal of a tree.

(Refer to the previous question.) As each node is traversed, its key value is printed as in the diagram above.

ALGORITHM Preorder

TreeNode : node

Boolean : done

Stack: stack

Node ← root

Done ← FALSE

WHILE NOT done

WHILE node NOT NULL

PRINT node

PUSH node onto stack

node ← left child node pointer of node

ENDWHILE

IF stack is empty

done ← TRUE

ELSE

node ← POP node from stack

node ← right child node pointer of node

ENDIF

ENDWHILE

END Preorder

**a)
**Modify the algorithm so that it will perform an in-order
traversal.

**b)
**Modify the algorithm so that it will perform a post-order
traversal. (Hint: As you leave a node to follow its left sub-tree,
update a value in the node to indicate that the node has been
visited.)

*Sorry the answer is not available at the moment…*

If you are able to** find the answer**, please make sure to post it here. So that your Juniors have smile on their lips and feel happy.

Spread the **'tradition of sharing'. **