(a) Design and implement a Java program that performs an inorder traversal of a binary tree without using recursion. The program must have time complexity O(n), where n is the number of nodes in the given binary tree. The program must have time complexity O(h), where h is the height of the tree.

Input. The input is a textual representation of a binary tree in the same format as in the problem above.

Sample input:

4

A5BD

B 3 C NONE

C 7 NONE NONE D 1 NONE NONE

Output. The output consists of a single line of space-separated tokens. Each token is the value of a corresponding node in the binary tree. The tokens appear in the order in which the corresponding nodes are visited during an inorder traversal of the input binary tree.

Sample output (for the above input): 7351

(b)

(c)

(d)

Note that the pseudo code should be meaningful in the sense that each step in the pseudo code should contribute to the solution. The pseudo code should not include steps that are there just to meet the time complexity requirements without contributing to the solution.

State what the time complexity of your program is and explain why. State what the space complexity of your program is and explain why.

Provide the pseudo code for an algorithm that performs an inorder traversal of a binary tree without using recursion, such that the algorithms time and space complexity are O(n). Explain why the algorithm you provide has this time and space complexity.