Inorder

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 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. A non-recursive printInOrder method is summarized in pseudocode form below.

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

Assignment:

1. Use the data file (file20.txt) from a previous binary tree lab to build the binary tree.

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

Instructions:

1. Turn in your source code and a run output. The run output should consist of the inorder output of the binary tree.