I am aware that most 'generic' BFS algorithms that use a queue also check for uniqueness of visitation to 'speed things up' as it were, but I'm a bit unclear as to how to implement such a method as I'm still a newbie to graph theory.

Beyond any general critique, I am curious about how I can modify the `iddfs_queue()` function as to include this property. Also, what is a common heuristic about order of functions in a file - i.e. should functions in the code match the way they are in the prototype list or is this a moot point as functions generally (except, e.g., static helper functions) get squandered off to header files?

There are three traversals of the tree printed to `stdout` in the following code, one showing pre-order traversal, another showing an IDDFS, and another showing a psuedo-IDDFS (which enqueues and dequeues nodes and works with them in that manner). A fictitious function `iddfs_stack()` would print in level-order and in reverse, but I have not implemented that here.

Finally, is the `typedef`s name of `QueueSpace` lacking in legibility?

 #include <stdio.h>
 #include <stdlib.h>
 #include <stdbool.h>
 
 typedef struct node Node;
 struct node {
 int item;
 struct node* left;
 struct node* right;
 };
 
 //queue ADT details
 typedef struct queueSpace QueueSpace;
 struct queueSpace {
 Node* node;
 QueueSpace* next;
 };
 typedef struct queue Queue;
 struct queue {
 QueueSpace* head;
 QueueSpace* tail;
 };
 
 //Tree functions
 Node* generateTree();
 Node* newNode(int value);
 Node* insertIntoTree(Node* root, Node* newNode);
 int treeHeight(Node* root);
 void printTree(Node* root);
 void printLevel(Node* root, int level);
 void freeTree(Node* root);
 void showcase();
 //Queue Functions
 Queue* createQueue();
 QueueSpace* createQueueSpace(Node* node);
 void enqueue(Queue* q, QueueSpace* space);
 Node* dequeue(Queue* q);
 void printQueue(Queue* q);
 //Primary Iteratively-Deepening Depth First Search functions
 void iddfs(Node* root);
 void iddfs_queue(Node* root);
 //generic helper functions
 int max(int a, int b);
 
 int main() {
 showcase();
 return EXIT_SUCCESS;
 }

 int max(int a, int b) {
 return (a > b) ? a : b;
 }
 
 void printQueue(Queue* q) {
 if ( !q || !q->head ) return;
 printf("\n\n///Printing the queue///\n");
 QueueSpace* head = q->head;
 while ( head ) {
 if ( head->node && head->node->item ) {
 printf("%d ", head->node->item);
 } else {
 printf(" NULL ");
 }
 head = head->next;
 }
 printf("\n///end of queue///\n");
 }
 
 void showcase() {
 Node* test = generateTree();
 printf("pre-order traversal: \n");
 printTree(test);
 printf("\niddfs traversal: \n");
 iddfs(test);
 printf("\niddfs (queue) traversal: \n");
 iddfs_queue(test);
 printf("\n");
 freeTree(test);
 }
 
 void freeTree(Node* root) {
 if ( !root ) return;
 freeTree(root->left);
 freeTree(root->right);
 free(root);
 }
 
 void printTree(Node* root) {
 if (!root) return;
 printf("%d ", root->item);
 printTree(root->left);
 printTree(root->right);
 }
 
 void iddfs(Node* root) {
 int i;
 for (i = 0; i <= treeHeight(root); i++) {
 printLevel(root, i);
 }
 }
 
 void iddfs_queue(Node* root) {
 Queue* q = createQueue(); 
 Node* tmp = root; 
 while ( tmp ) {
 printf("%d ", tmp->item);
 if ( tmp->left )
 enqueue(q, createQueueSpace(tmp->left));
 if ( tmp->right ) 
 enqueue(q, createQueueSpace(tmp->right));
 tmp = dequeue(q);
 }
 }
 
 //creates an empty queue 
 Queue* createQueue() {
 Queue* q = malloc(sizeof(*q));
 q->head = NULL;
 q->tail = NULL;
 return q;
 }
 
 //generate a space in the queue with node
 QueueSpace* createQueueSpace(Node* node) {
 QueueSpace* space = malloc(sizeof(*space));
 space->node = node;
 space->next = NULL;
 return space;
 }
 
 //enqueue single node onto q
 //currently does not enforce a size limit
 void enqueue(Queue* q, QueueSpace* space) {
 if ( !q || !space ) return;
 if ( !q->head ) {
 q->head = space;
 q->tail = space;
 } else {
 q->tail->next = space;
 q->tail = space;
 }
 }
 
 //Dequeue the head of q and reassign head
 Node* dequeue(Queue* q) {
 if ( !q || !q->head ) return NULL;
 Node* head = q->head->node;
 q->head = q->head->next;
 return head;
 }
 
 void printLevel(Node* root, int level) {
 if (!root) {
 return;
 } 
 if ( level == 0 ) {
 printf("%d ", root->item);
 } else if ( level > 0 ) {
 printLevel(root->left, level-1);
 printLevel(root->right, level-1);
 } //else, do nothing.
 }
 
 Node* insertIntoTree(Node* root, Node* newNode) {
 if ( !root ) {
 return root;
 } else {
 if ( newNode->item < root->item ) {
 if ( root->left ) {
 insertIntoTree(root->left, newNode);
 } else {
 root->left = newNode;
 }
 } else {
 if ( root->right ) {
 insertIntoTree(root->right, newNode);
 } else {
 root->right = newNode;
 }
 }
 return root;
 }
 }
 
 Node* newNode(int value) {
 Node* newNode = malloc(sizeof(*newNode));
 newNode->item = value;
 newNode->left = NULL;
 newNode->right = NULL;
 return newNode;
 }
 
 Node* generateTree() {
 Node* root = newNode(5);
 insertIntoTree(root, newNode(8));
 insertIntoTree(root, newNode(6));
 insertIntoTree(root, newNode(2));
 insertIntoTree(root, newNode(9));
 insertIntoTree(root, newNode(1));
 insertIntoTree(root, newNode(0));
 return root;
 }
 
 int treeHeight(Node* root) {
 if ( !root ) {
 return -1;
 } else {
 return max(treeHeight(root->left), treeHeight(root->right)) + 1;
 }
 }