Could someone tell me why the binary tree I am creating in this code using it's preorder and postorder is not being created in the desired way?

Question

I have written this code to create a binary tree using given preorder and inorder traversals. According to the dry run I do, there is no problem, and the tree should be created properly. But it is not happening that way. I have printed the inorder of the tree just to check if the tree has been created of the tree. But instead of the inorder, the postorder is being printed. On further investigation I found that the tree itself is not created rightly, that is why the error is coming. There is nothing on the right part of the root which is created. But according to the dry run, there is no problem. Could someone help me find my mistake?

Sample Input: a b d e f c g h j l k d b f e a g c l j h k

Output: dfebgljkhca

     #include <stdio.h>

typedef struct Node
{
    int data;
    struct node *left;
    struct node *right;
}node;
typedef node *tree;
tree root=NULL;

char pre[11];
char in[11];

static int i;

void create( tree temp, int start_left, int end_left, int start_right, int end_right )
{
    if ( start_left <= end_left )
    {
        temp->left= (tree) malloc(sizeof( node ));
        temp=temp->left;
        temp->left=NULL;
        temp->right=NULL;
        int j;
        for ( j=start_left; j<=end_left; j++)
        {
            if ( pre[i]==in[j] )
            {
                temp->data=pre[i];
                break;
            }
        }
        i++;
        create( temp, start_left, j-1, j+1, end_left );

    }
    if ( start_right <= end_right )
    {
        temp->right= (tree) malloc(sizeof( node ));
        temp=temp->right;
        temp->left=NULL;
        temp->right=NULL;
        int j;
        for ( j=start_right; j<=end_right; j++)
        {
            if ( pre[i]==in [j] )
            {
           temp->data=pre[i];
                break;
            }
        }
        i++;
        create( temp, start_right, j-1, j+1, end_right );
    }
    return ;
}

void inorder_print(tree temp)
{
    if ( temp!=NULL )
    {
        inorder_print(temp->left);
        printf("%c",temp->data);
        inorder_print(temp->right);
    }
}

int main()
{

    for( i=0; i<11; i++)
    {
        scanf("%c", &pre[i]);
        fflush(stdin);
    }

    for( i=0; i<11; i++)
    {
        scanf("%c", &in[i]);
        fflush(stdin);
    }
    int j;
    for( j=0; j<11; j++)
    {
        if( pre[0]==in[j] )
        {
            root= (tree) malloc(sizeof( node ));
            root->data=pre[0];
            root->left=NULL;
            root->right=NULL;
            break;
        }
    }
    i=1;
    create( root, 0, j-1, j+1, 10);
    inorder_print(root);
    return 0;
}

You casted the result of malloc. And this legit hurt you this time. You haven't included stdlib. I just hope your heap is located 4 GB+ — Ajay Brahmakshatriya, Apr 13 '17 at 20:23
Can you provide information as to what is actually wrong? Consider checking the [help], especially how to create a [mcve], and [ask] — Delioth, Apr 13 '17 at 20:24
@AjayBrahmakshatriya note that he did `typedef node *tree`, so the cast is actually legit... Ugly, but legit. — silel, Apr 13 '17 at 20:27
Notes: `scanf("%c", &in[i]);` will read *everything* including any (possibly previous) `newline`, and `fflush(stdin);` is non-standard. — Weather Vane, Apr 13 '17 at 20:27
@silel the cast is legit but unnecessary. In this case it infact hurted him because it hid the warning about an int being casted to tree (pointer) which occurred because he forgot to include stdlib. — Ajay Brahmakshatriya, Apr 13 '17 at 20:29
@silel Now say the heap is at a position after 4GB, the compiler will assume that malloc returns an integer and it will chop off the higher bits. — Ajay Brahmakshatriya, Apr 13 '17 at 20:30
Is the sample input really space-separated? Unless you instruct `scanf` to ignore whitespace by adding a space in `scanf(" %c", &in[i]);` it will read every space and newline as input. — Weather Vane, Apr 13 '17 at 20:32
@AjayBrahmakshatriya I just read [this](http://stackoverflow.com/questions/21327899/when-we-used-malloc-without-declaring-stdlib-h-header-file-compiler-returns-an-i) thread. I must admit I still don't see how the position of the heap is or is not going to be a problem. — silel, Apr 13 '17 at 20:53
@silel on most architectures `int` is 32 bits and on 64 bit architectures pointers are 64 bits. Now what does the compiler see - malloc returns an int (32 bit) the user has casted it to 64 bits. So it will zero expand the bits. But the malloc had actually returned 64 bits. The compiler will ignore the higher bits. And it would be bad if the heap is after 4 GB since the higher bits in that case will be non zero. — Ajay Brahmakshatriya, Apr 13 '17 at 20:56
@silel see this http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc discussion on why to not cast the result of malloc. In the first answer the 4th point elaborates what I said. — Ajay Brahmakshatriya, Apr 13 '17 at 20:58
@WeatherVane no, I actually press enter after every entry in the input — Nayan Garg, Apr 15 '17 at 02:02

score 0 · Answer 1 · answered Apr 13 '17 at 22:06

What about something more generalized? My suggestion has the following output:

prorder:
a a b b d c c d e e f f g g h h j j l k k l 
inorder:
a a b b c c d d e e f f g g h h j j k k l l 
   [a]                            
 +--+-----+                    
[a]      [b]                   
       +--+-----------+        
      [b]            [d]       
                +-----+-----+
               [c]         [e]
             +--+--+     +--+-----+
            [c]   [d]   [e]      [f]
                               +--+-----+
                              [f]      [g]
                                     +--+-----+
                                    [g]      [h]
                                           +--+-----+
                                          [h]      [j]
                                                 +--+-----------+
                                                [j]            [l]
                                                          +-----+
                                                         [k]
                                                       +--+--+ 
                                                      [k]   [l]

And the code is:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct      s_tree
{
    void            *content;
    size_t          content_size;
    struct s_tree   *left;
    struct s_tree   *right;
}                   t_tree;

/*
** Tree content casted to given type
*/

#define TCONT(tree, t_type) ((t_type)((tree)->content))

/*
** Helpers
*/

void    *ft_memdup(void const *ptr, size_t size)
{
    void            *result;

    result = (void*)malloc(size);
    if (result == NULL)
        return (NULL);
    memcpy(result, ptr, size);
    return (result);
}

t_tree  *ft_tree_new(void const *content, size_t content_size)
{
    t_tree  *result;

    result = (t_tree*)malloc(sizeof(t_tree));
    if (result == NULL)
        return (NULL);
    result->left = NULL;
    result->right = NULL;
    if (content == NULL)
    {
        result->content = NULL;
        result->content_size = 0;
    }
    else
    {
        result->content = ft_memdup(content, content_size);
        result->content_size = content_size;
    }
    return (result);    
}

void    ft_tree_add(
            t_tree **root,
            t_tree *new_branch,
            int (*cmp)(void*, void*))
{
    if (*root == NULL)
        *root = new_branch;
    else
    {
        if (cmp((*root)->content, new_branch->content) >= 0)
            ft_tree_add(&(*root)->left, new_branch, cmp);
        else
            ft_tree_add(&(*root)->right, new_branch, cmp);
    }
}

void    ft_tree_map(t_tree *root, void (*f)(void*), char *map)
{
    int     i;

    if (root != NULL)
        for (i = 0; map[i]; i++)
        {
            switch (map[i])
            {
                case 'R':
                    f(root->content);
                    break;
                case 'r':
                    ft_tree_map(root->right, f, map);
                    break;
                case 'l':
                    ft_tree_map(root->left, f, map);
                    break;
            }
        }
}

/*
** Print tree function
*/

int _print_t(t_tree *tree, int is_left, int offset, int depth, char s[50][256])
{
    char    b[50];
    int     width = 3;
    int     i;

    if (!tree)
        return 0;

    sprintf(b, "[%s]", TCONT(tree, char*));

    int left  = _print_t(tree->left,  1, offset,                depth + 1, s);
    int right = _print_t(tree->right, 0, offset + left + width, depth + 1, s);

    for (i = 0; i < width; i++)
        s[2 * depth][offset + left + i] = b[i];

    if (depth && is_left)
    {
        for (i = 0; i < width + right; i++)
            s[2 * depth - 1][offset + left + width/2 + i] = '-';
        s[2 * depth - 1][offset + left + width/2] = '+';
        s[2 * depth - 1][offset + left + width + right + width/2] = '+';
    } else if (depth && !is_left)
    {
        for (int i = 0; i < left + width; i++)
            s[2 * depth - 1][offset - width/2 + i] = '-';

        s[2 * depth - 1][offset + left + width/2] = '+';
        s[2 * depth - 1][offset - width/2 - 1] = '+';
    }
    return left + width + right;
}

void print_tree(t_tree *tree)
{
    char s[50][256];

    for (int i = 0; i < 50; i++)
        sprintf(s[i], "%100s", " ");

    _print_t(tree, 0, 0, 0, s);

    for (int i = 0; i < 50; i++)
        printf("%s\n", s[i]);
}

//end of print tree function

void    print_str(char *str)
{
    printf("%s ", str);
}

int     main()
{
    t_tree  *root;
    char    input[] = "abdefcghjlkdbfeagcljhk";
    char    tmp[2];
    int     i;

    tmp[1] = 0;
    root = NULL;
    for (i = 0; input[i]; i++)
    {
        tmp[0] = input[i];
        ft_tree_add(&root,
            ft_tree_new(tmp, strlen(tmp) + 10),
            (int (*)(void*, void*))(&strcmp));
    }

    //Preorder
    printf("preorder:\n");
    ft_tree_map(root, (void (*)(void*))(&print_str), "Rlr");
    printf("\n");

    //Inorder
    printf("inorder:\n");
    ft_tree_map(root, (void (*)(void*))(&print_str), "lRr");
    printf("\n");

    print_tree(root);
}

If you want to change the way of insertion, make your own comparison function and change &strcmp with &your_function.

Thanks for your suggestion Emil, but I actually wanted to know what the problem in my code was. — Nayan Garg, Apr 15 '17 at 02:06

Could someone tell me why the binary tree I am creating in this code using it's preorder and postorder is not being created in the desired way?

1 Answers1