TreeTraversal

Background:

Any recursive algorithm can be reduced to a linear sequence of events. It will be longer and more difficult to follow, but recursive solutions can be rewritten as iterative solutions if a stack is available for use. In this lab assignment, implement a non-recursive printInOrder, printPreOrder and printPostOrder method using a stack. After completing the lab, a greater appreciation for recursion and what it will accomplish for you should have been achieved.

You will work with the binary tree code that was implemented in Lesson AB30, Binary Trees. Pseudo-code for each non-recursive tree traversal is shown below.

Inorder traversal

declare a Stack of TreeNode intitalized as empty
declare a temp TreeNode initialized to root

do
  while temp is not null
    push a copy of temp onto the stack
    set temp to temp’s left subtree

  if the stack is not empty
    pop the stack into temp
    print the contents of temp
    set temp to temp’s right subtree
until temp is null and the stack is empty

Preorder traversal

declare a Stack of TreeNode intitalized as empty
declare a temp TreeNode initialized to root

do
  while temp is not null
    print the contents of temp
    push a copy of temp onto the stack
    set temp to temp’s left subtree

  if the stack is not empty
    pop the stack into temp
    set temp to temp’s right subtree
until temp is null and the stack is empty

Postorder traversal

In a postorder traversal of a binary tree, for each node, first the left subtree is visited, then the right subtree is visited, and then the node is visited. As in the case of an inorder traversal, in a postorder traversal, the first node visited is the leftmost node of the binary tree. Because—for each node—the left and right subtrees are visited before visiting the node, we must indicate to the node whether the left and right subtrees have been visited. After visiting the left subtree of a node and before visiting the node, we must visit its right subtree. Therefore, after returning from a left subtree,we must tell the node that the right subtree needs to be visited, and after visiting the right subtree we must tell the node that it can now be visited. To do this, other than saving a reference to the node (to get back to the right subtree and to the node itself), we also save an integer value of 1 before moving to the left subtree and an integer value of 2 before moving to the right subtree. Whenever the stack is popped, the integer value associated with that reference is popped as well. This integer value tells whether the left and right subtrees of a node have been visited.

declare a Stack of TreeNode intitalized as empty
declare a Stack of Integer intitalized as empty
declare a current TreeNode initialized to root
declare an integer v initialized to 0

if current is not null
  push current onto TreeNode stack
  push 1 onto Integer stack
  set current to current’s left subtree

while stack is not empty
  if current is not null and v is 0
    push current and 1 onto stack
    set current to current’s left subtree
  else
    pop stack into current and v
    if v is 1
      push current and 2 onto stack
      set current to current’s right subtree
      set v to 0
    else
      print the contents of current

Assignment:

1. Use the data file (fileC.txt) from a previous binary tree lab to build the binary tree of characters ordered by letter.

2. Write the code for the non-recursive printInOrder method. Use (fileC.txt) to test your program.

3. Write the code for the non-recursive printPreOrder method. Use (fileC.txt) to test your program.

4. Write the code for the non-recursive printPostOrder method. Use (fileC.txt) to test your program.

Instructions:

1. Submit your source code and a run output. The run output should consist of the printInOrder, printPreOrder, and printPostOrder output of the binary tree.