Binary Tree In-order Rearrange

increasingBST.c

#define MAX_ARR_SIZE 400 

/* create a stack */
typedef struct {
    int top;
    struct TreeNode array[MAX_ARR_SIZE];
} Stack;

int node_comparator(const void *p, const void *q);

struct TreeNode *increasingBST(struct TreeNode *root) {
    /* add all the nodes to an array via DFT */
    int i, sorted_pos = 0;
    struct TreeNode *start, *cur;
    struct TreeNode sorted_nodes[MAX_ARR_SIZE];
    Stack *node_stack = malloc(sizeof(Stack));
    
    node_stack->top = -1; 
    node_stack->array[++node_stack->top] = *root;
    cur = malloc(sizeof(struct TreeNode));
    
    while (node_stack->top != -1) {
        /* "pop" node off stack */
        *cur = node_stack->array[node_stack->top--];
        printf("Current node value: %d\n", cur->val);
        
        /* add node to array */
        sorted_nodes[sorted_pos++] = *cur;
        printf("New node in sorted_nodes with val %d\n", sorted_nodes[sorted_pos-1].val);
        
        /* add right and left node to stack, if present */
        if (cur->right != NULL) {
            printf("Adding right node to stack. Value: %d\n", cur->right->val);
            node_stack->array[++node_stack->top] = *cur->right;
        }
        printf("Current Node has value %d on sorted_pos: %d\n", cur->val, sorted_pos);
        
        if (cur->left != NULL) {
            printf("Adding left node to stack. Value: %d\n", cur->left->val);
            node_stack->array[++node_stack->top] = *cur->left;
        }
    }
    printf("Sorted Nodes 0 val: %d\n", sorted_nodes[0].val);
    
    
    /* sort the array the holds the nodes (sorted_nodes) */
    qsort(sorted_nodes, sorted_pos,
          sizeof(struct TreeNode), node_comparator);
    
    printf("post sort Nodes 0 val: %d\n", sorted_nodes[0].val);
    
    printf("Sorted pos %i\n", sorted_pos); 
    /* re-arrange nodes after sort */
    for (i=0; i<=sorted_pos-1; i++) {
        printf("Iteration: %d\n", i);
        if (i == sorted_pos-1)
            sorted_nodes[i].right = NULL;
        else {
            sorted_nodes[i].right = &sorted_nodes[i+1];
            sorted_nodes[i].left = NULL;
        }
    }
    
    root = &sorted_nodes[0];
    return root;
 
}

/**********************************************************
 * comparator function for qsort. qsort prototype:        * 
 *                                                        * 
 * void qsort(void *base, size_t nmemb, size_t size,      * 
 *            int (*compar)(const void *, const void *)); *
 **********************************************************/
int node_comparator(const void *n1, const void *n2)
{
    struct TreeNode *node1 = n1;
    struct TreeNode *node2 = n2;
    
    printf("Comparing node val %d and %d\n", node1->val, node2->val);
    
    if (node1->val < node2->val)
        return -1;
    else if (node1->val == node2->val)
        return 0;
    else
        return 1;
}

increasingBSTdescription.txt

/*
 * PROBLEM DEFINITION:                                      
 * Given a binary search tree, rearrange the tree in        
 * in-order so that the leftmost node in the tree is now    
 * the root of the tree, and every node has no left child 
 * and only 1 right child.
 *
 * Example 1:
 * Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]
 * 
 *        5
 *       / \
 *     3    6
 *    / \    \
 *   2   4    8
 *  /        / \ 
 * 1        7   9
 * 
 * Output: [1,null,2,null,3,null,4,null,
 *          5,null,6,null,7,null,8,null,9]
 * 
 *  1
 *   \
 *    2
 *     \
 *      3
 *       \
 *        4
 *         \
 *          5
 *           \
 *            6
 *             \
 *              7
 *               \
 *                8
 *                 \
 *                  9  


 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 *
 */