Iteratively-Deepening Depth First Search (queue and non-queue)

Question

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 typedefs 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;
    }
}

Answer 1

Some minor observations -

struct definitions

typedef struct queue Queue;
struct queue {
    QueueSpace* head;
    QueueSpace* tail;
};

Why not do something like this:

typedef struct Queue {
    QueueSpace* head;
    QueueSpace* tail;
} Queue;