BST nodes are not saving when trying to create a preorder traversal of a previous tree in c

Question

I am trying to see if tree A is the preorder traversal of tree B and to do so, I created two trees which during a transversal were supposed to save the values. However, after hours of debugging I found out that the trees values were ALWAYS 0. I am confused as to why the trees values are 0. I've done a multitude of print statements (some of which I've left in the code posted below) and I just cannot seem to pinpoint why this is happening. Can someone please nudge me in the correct direction? I thought maybe the function was deleting variables as it exited and in effort to get to the bottom of the issue I had the preorder function return the tree ( as seen below), however, the output is ALWAYS 0 for the tree.

Code:

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;
int tree_diff(node *a, node *b)
{
    if (a == NULL && b == NULL)
        return 0;

    else if (a == NULL || b == NULL)
        return 1;


    else if (a->data != b->data)
        return 1;
    printf("A %d , B %d", a->data, b->data);

        return tree_diff(a->left, b->left) || tree_diff(a->right, b->right);
}

node *preorder_recursive(node *root, node *A)
{
    if (root == NULL)
        return A;

    printf("root %d ", root->data);
    A = root;
    printf("= data %d\n", A->data);
    preorder_recursive(root->left, A->left);
    preorder_recursive(root->right, A->right);
}

void postorder_recursive(node *root, node *B)
{
    if (root == NULL)
        return;
    B = root;
    postorder_recursive(root->left, B->left);
    postorder_recursive(root->right, B->right);
    printf("root %d ", root->data);
    printf("= data %d\n", B->data);
}

int kindredSpirits(node *a, node *b)
{

  // Get the preorder of a
  node *A = malloc(sizeof(node));
  A = preorder_recursive(a, A);

  // Get the postorder of b
  printf("\n\n");
  node *B = malloc(sizeof(node));
  postorder_recursive(b, B);

if(tree_diff(A,B) == 1)
  return 0;
else
  return 1;
}

The test case:

#include <stdio.h>
#include <stdlib.h>
#include "KindredSpirits.h"
  node *create_node(int data)
{
    node *n = malloc(sizeof(node));

    n->data = data;
    n->left = n->right = NULL;

    return n;
}

node *forest_fire(node *root)
{
    if (root == NULL)
        return NULL;

    forest_fire(root->left);
    forest_fire(root->right);
    free(root);
}

int main(void)
{
    node *root;

    root = create_node(23);
    root->left = create_node(12);
    root->left->left = create_node(5);
    root->left->right = create_node(18);
    root->right = create_node(71);
    root->right->right = create_node(56);

    printf("%s\n", !kindredSpirits(root, root) ? "Success!" : "fail whale :(");

    forest_fire(root);

    return 0;
}

Answer 1

Here's a code fragment that should get you started:

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

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

typedef struct list {
    int lst_max;                        // maximum number of allocated cells
    int lst_cur;                        // current number of filled cells
    int *lst_base;                      // traversal list
} list;

list list_a = { 0, 0, NULL };
list list_b = { 0, 0, NULL };

void
list_append(list *lst,int data)
{
    int newidx;

    newidx = lst->lst_cur;

    if (newidx >= lst->lst_max) {
        lst->lst_max += 100;
        lst->lst_base = realloc(lst->lst_base,sizeof(int) * lst->lst_max);
        if (lst->lst_base == NULL) {
            printf("list_append: malloc error\n");
            exit(1);
        }
    }

    lst->lst_base[newidx] = data;

    lst->lst_cur = newidx + 1;
}

void
preorder_recursive(node *root,list *lst)
{

    if (root == NULL)
        return;

    list_append(lst,root->data);
    preorder_recursive(root->left,lst);
    preorder_recursive(root->right,lst);
}

void
postorder_recursive(node *root,list *lst)
{

    if (root == NULL)
        return;

    postorder_recursive(root->left,lst);
    postorder_recursive(root->right,lst);
    list_append(lst,root->data);
}

int
main(void)
{

    preorder_recursive(a,&list_a);
    postorder_recursive(b,&list_b);

    // compare list_a and list_b ...

    return 0;
}