Why I am unable to get the binary tree level order traversal from following code?

Question

I am trying to do a level order traversal of a binary search tree and return the final result in a multi-dimensional array. eg. if root node is 2 and nodes at level 1 are 1,4 then it should return [[2], [1,4]] as returnColumnSizes from the code. I am new in data structures and don't have command in using malloc function as well. Any help will be appreciated. Thanks :)

int height(struct TreeNode *h){
    if (h == NULL) return 0;
    int l = height(h->left);
    int r = height(h->right);
    if (l > r)
        return l+1;
    else
        return r+1;
}

int *ordercalc(struct TreeNode *root, int level){
    if (root == NULL) return NULL;
    int i = 0, arr[100];
    if (level == 1)
        arr[i++] = root->val;
    else if(level > 1){
        ordercalc(root->left, level-1);  //decrease the level one per call to print data when it
        ordercalc(root->right, level-1);  // reaches proper level
    }
    return arr;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (*returnSize == 0) return NULL;
    **returnColumnSizes = (int **)malloc(*returnSize * sizeof(int *));
    for (int i=0;i<height(root)+1;i++){
        returnColumnSizes[i] = (int *)malloc(sizeof(int) * 10);
        returnColumnSizes[i] = ordercalc(root, i);
    }
    return returnColumnSizes;
}

Answer 1

height looks good.

levelOrder looks okay, although i<height(root)+1; computes the height of root again and again in the loop even though it doesn't change. Also, malloc(sizeof(int) * 10); doesn't seem sufficiently dynamic for large trees (we'll come back to this later).

ordercalc needs to be re-considered. The function has arr[100]; allocated on its stack frame, then

if (level == 1)
    arr[i++] = root->val;

and

return arr;

I can see you're trying to fill the levels based on the height, which is the right idea. However:

1. Returning a stack-allocated array is undefined behavior. When the call returns, all data on its frame cannot be accessed. You'll need to malloc on the heap and return a pointer if you want to do this.
2. arr[i++] = root->val; puts the root at arr[0] but nothing else ever happens with this array, so the intent is unclear.
3. Hardcoding 100 for the array size seems a mistake. Surely there is some tree with a level large enough to overflow this buffer, assuming you intend to fill it up beyond the root. When you do switch to malloc, you'll probably need to plan to realloc.

Instead of returning results from this function, it seems that passing in a pointer to the pre-allocated result structure is simplest.

A way to simplify the reallocation and size management is to approach the problem with multiple passes. Here's the game plan:

1. Get the tree height.
2. Allocate the result and column size arrays to match tree height.
3. Perform a second traversal and set the result column lengths for each level.
4. Allocate each level to match the size determined in step 3.
5. Perform a final pass to populate the pre-allocated result levels.

Here's the code:

int height(struct TreeNode *root) {
    if (root) {
        int left = height(root->left);
        int right = height(root->right);
        return 1 + (left > right ? left : right);
    }

    return 0;
}

void set_col_lens(struct TreeNode *root, int *res_col_lens, int depth) {
    if (root) {
        res_col_lens[depth]++;
        set_col_lens(root->left, res_col_lens, depth + 1);
        set_col_lens(root->right, res_col_lens, depth + 1);
    }
}

void fill_levels(struct TreeNode *root, int **res, int *last_items, int level) {
    if (root) {
        int last_item = last_items[level]++;
        res[level][last_item] = root->val;
        fill_levels(root->left, res, last_items, level + 1);
        fill_levels(root->right, res, last_items, level + 1);
    }
}

int **level_order(struct TreeNode *root, int *res_len, int **res_col_lens) {
    if (!root) {
        *res_len = 0;
        return NULL;
    }

    *res_len = height(root);
    int **res = malloc(sizeof(*res) * (*res_len));
    *res_col_lens = calloc(*res_len, sizeof(**res_col_lens));
    int *last_items = calloc(*res_len, sizeof(*last_items));
    set_col_lens(root, *res_col_lens, 0);

    for (int i = 0; i < *res_len; i++) {
        res[i] = malloc(sizeof((*res)[i]) * (*res_col_lens)[i]);
    }

    fill_levels(root, res, last_items, 0);
    free(last_items);
    return res;
}

One benefit of this is that the problem is broken into simple, distinct steps.

Another approach which I think is more natural is to use a queue and perform a breadth-first traversal in one stack frame. The problem then becomes writing a queue abstraction in C, which is not difficult but does take a bit of fussing.