function to create array of post order binary tree

Question

Im trying to create a recursive function that creates an array of post order integers from a given tree. This is the code:

//structure
typedef struct node
{
    // Each node holds a single integer.
    int data;

    // Pointers to the node's left and right children.
    struct node *left, *right;
} node;

// preorder_recursive is same as postorder_recursive(), except
// array[i] comes before the recursive calls

int *postorder_recursive(node *root)
{
    int *array = malloc(sizeof(node) * node_count(root)); // node_count(root) counts nodes in binary tree
    int i = 0;
    if (root == NULL)
        return 0;

    while (root != NULL)
    {
        postorder_recursive(root->left);
        postorder_recursive(root->right);
        array[i] = root->data;
        i++;
    }
    return array;
}

// returns 1 if pre order = post order, returns 0 otherwise
int compare(node *a, node *b)
{
    int i = 0;
    int *preArray, *postArray;
    if (node_count(a) != node_count(b))
        return 0;
    preArray = preorder_recursive(a);
    postArray = postorder_recursive(b);
    for (i = 0; i < node_count(a); i++)
    {
        if (preArray[i] != postArray[i])
            return 0;
    }

  free(preArray);
  free(postArray);

    return 1;
}

I am not entirely sure if the error is in this function, but if it is, it's probably due to the while loop. Any help would be great.

Edit: Ive included a lot more code. The purpose of this is to compare an array of post order to an array of pre-order.

We need more code, like your structure or something

Gonçalo Bastos
– Gonçalo Bastos

2020-11-15 17:41:11 +00:00
Commented Nov 15, 2020 at 17:41 — Gonçalo Bastos
– Gonçalo Bastos, Commented Nov 15, 2020 at 17:41

G. Sliepen · Accepted Answer · 2020-11-15 18:06:09Z

Your function postorder_recursive() is creating a new array every time it is called. Furthermore, while(root != NULL) will loop forever for non-empty trees, if it weren't for the fact that it writes past the end of array and cause a segmentation fault at some point.

The solution is to split the function into one that creates the array, and then another function that recursively fills in the array, like so:

static size_t postorder_recursive(const node *root, int *array, size_t index) {
    if (root == NULL)
        return index;

    index = postorder_recursive(root->left, array, index);
    index = postorder_recursive(root->right, array, index);
    array[index++] = root->data;

    return index;
}

int *postorder_to_array(const node *root)
{
    int *array = malloc(sizeof(node) * node_count(root));
    postorder_recursive(root, array, 0);
    return array;
}

Collectives™ on Stack Overflow

function to create array of post order binary tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related