Thread: Tree sort help

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    10

    Tree sort help

    Hi Guys,

    I have a problem for school and I am not able to solve it.

    "You have been provided with a header file Tree.h containing only the function prototypes needed for a binary tree sorting algorithm. Create a class Tree.c that includes the header file and implements the function calls. You are to retain the same signatures and do not add any other functions. Each function prototype has comments as documentation. You can create an integer array with fixed values for testing purposes. To sort the array, you should only call bstSort. "

    the Tree.h file is something like this:
    Code:
    #ifndef_TREE_H_
    #define_TREE_H_
        /*
           A binary tree node structure for integer values. Every node
           has a pointer to the left child node and right child node.
           If the value to be added is smaller than the value of the
           current node then it is placed in the left node, otherwise
           it goes in the right node. The first node of the tree
           is called the root node. Nodes with no children are leaf nodes.
         */
    struct Node {
      int val;
      struct Node *left, *right;
    };
    
    /*
       Sorts an array of integers using a binary tree.
       *arr is a pointer to an integer array.
       n is the number of integers in the array.
     */
    void bstSort(int *arr, int n);
    
    /* 
       Adds an integer value to a tree node. 
       If n is null then it is created and assigned to the value.
       If the value is smaller than the node value then it is inserted
       to the left node of the current node. Otherwise it is inserted
       to the right node of the current node.
     */
    struct Node *insert(struct Node *n, int val);
    
    /*
       Does an inorder traversal of the tree structure and
       fills in the array with the sorted values.
       Pos is a reference to the current position.
     */
    void storeSorted(struct Node *n, int *arr, int *pos);
    
    /*
       Destroys the binary tree structure by doing an inorder traversal
       and frees the dynamically allocated memory of each node.
     */
    void bstDestroy(struct Node *n);
    
    #endif

    I tried to do it by myself following some tutorial but all of them are different from the structure I have to follow and I am losing my mind for the past few days

    Could any of you help me with this?
    Thank you very much.
    Last edited by Salem; 04-07-2019 at 04:56 AM. Reason: Removed crayola

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,158
    Instead of following a tutorial, why not follow the instructions that your teacher helpfully provided in the comments? The key is to think of how to use insert, storeSorted, and bstDestroy to implement bstSort.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2019
    Posts
    10
    Hi laser, the problem is that I do not completely understand how this works and I tried to follow the tutorials to try and understand what should I do but the problem is that everything is different than the implementation, therefore I am getting lost.

    Any help would be appreciated.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,158
    The idea is that if you keep inserting values into the binary tree such that "If the value is smaller than the node value then it is inserted to the left node of the current node. Otherwise it is inserted to the right node of the current node", then if you do "an inorder traversal of the tree structure and fills in the array with the sorted values", you would have sorted the array with the help of the binary tree.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2019
    Posts
    10
    Quote Originally Posted by laserlight View Post
    The idea is that if you keep inserting values into the binary tree such that "If the value is smaller than the node value then it is inserted to the left node of the current node. Otherwise it is inserted to the right node of the current node", then if you do "an inorder traversal of the tree structure and fills in the array with the sorted values", you would have sorted the array with the help of the binary tree.
    I am almost there.

    I wrote the below code but it gives me some errors while running, I just need to double check it and then understand how to destroy the nodes using the bstDestroy

    Code:
    #include <stdio.h>
    int main()
    {    
        int arr[] = {10, 5, 8, 20, 16, 70, 50, 9};
        int n = sizeof(arr)/sizeof(arr[0]);
        
        bstSort(arr, n);
    }
    
    
    struct Node {
        int val;
        struct Node *left, *right;
    };
    
    
    void bstSort(int *arr, int n)
    {
        struct Node *root = NULL;
        
        root = insert(root, arr[0]);
        for (int i=1; i<n; i++) 
            insert(root, arr[i]);
        
        int i = 0; 
        storeSorted(root, arr, i); 
        
    }
    
    
    struct Node * insert(struct Node *n, int val)
    {    
        if (val < n->val) 
            n->left  = insert(n->left, val); 
        else if (val > n->val) 
            n->right = insert(n->right, val); 
          
        return n;     
    }
    
    
    void storeSorted(struct Node *n, int *arr, int *pos)
    {
        
        if (n != NULL) 
        { 
            storeSorted(n->left, arr, *pos); 
            arr[*pos] = n->val; 
            storeSorted(n->right, arr, *pos); 
        }     
        
    }

  6. #6
    I'm a computer snoopfrogg's Avatar
    Join Date
    Feb 2019
    Posts
    29
    Quote Originally Posted by masterxfile View Post
    I am almost there.

    I wrote the below code but it gives me some errors while running, I just need to double check it and then understand how to destroy the nodes using the bstDestroy
    Your first post states:
    Code:
    /*
    
       Destroys the binary tree structure by doing an inorder traversal
    
       and frees the dynamically allocated memory of each node.
     */
    void bstDestroy(struct Node *n);
    Inorder traversals work in the following order (left, root, right).

    Here's a general idea of how the algorithm works:
    1. Traverse the left subtree, i.e., call Inorder(left-subtree)
    2. Visit the root
    3. Traverse the right subtree, i.e., call Inorder(right-subtree)


    Hope this helps.

    Also, I think your insert function is incorrect. The right and left insertions are correct but your instructions state:

    If n is null then it is created and assigned to the value.
    If I'm not mistaken, you'll have to check if the node is null and then perform a normal binary tree insertion. (Correct me if I'm wrong)
    Last edited by snoopfrogg; 04-08-2019 at 03:22 PM.
    "One of the best programming skills you can have is knowing when to walk away for awhile."

  7. #7
    Registered User
    Join Date
    Apr 2019
    Posts
    10
    Thank you snoopfrogg,

    You were right I had to create a new node.

    Code:
    #include <stdio.h>#include <stdlib.h>
    struct Node {
      int val;
      struct Node *left, *right;
    };
    
    void bstSort(int *arr, int n);
    struct Node *insert(struct Node *n, int val);
    void storeSorted(struct Node *n, int *arr, int *pos);
    void bstDestroy(struct Node *n);
    
    int main()
    {
      int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
      int n = sizeof(arr) / sizeof(arr[0]);
    
      bstSort(&arr, n);
    
      for (int ii = 0; ii < n; ii++)
        printf("%d\n", arr[ii]);
    
      getchar();
      return 0;
    }
    
    void bstSort(int *arr, int n)
    {
      struct Node *root = NULL;
    
      // root = insert(root, arr[0]);
    
      for (int i = 0; i < n; i++)
        insert(root, arr[i]);
    
      storeSorted(root, arr, &arr[0]);
      bstDestroy(root);
    }
    
    struct Node *insert(struct Node *n, int val)
    {
      if (n == NULL) {
        n = malloc(sizeof(struct Node));
        (n)->left = NULL;
        (n)->val = val;
        (n)->right = NULL;
      } else {
        if (val < n->val)
          n->left = insert(n->left, val);
        else if (val > n->val)
          n->right = insert(n->right, val);
      }
    
      return n;
    }
    
    void storeSorted(struct Node *n, int *arr, int *pos)
    {
      if (n != NULL) {
        storeSorted(n->left, arr, pos);
        arr[*pos] = n->val;
        storeSorted(n->right, arr, pos);
    
      }
    }
    
    void bstDestroy(struct Node *n)
    {
      if (n == NULL)
        return;
      if (n->left != NULL)
        bstDestroy(n->left);
      if (n->right != NULL)
        bstDestroy(n->right);
      free(n);
      return;
    }
    Now I have only one problem left.
    The code above works and it creates the tree structure as needed, the only thing is that in the storeSorted function the array is sorted but it remains there.

    When I go back to the top of the code it is not sorted so I might need to do some more research.
    Last edited by Salem; 04-09-2019 at 08:10 AM. Reason: Removed crayola

  8. #8
    I'm a computer snoopfrogg's Avatar
    Join Date
    Feb 2019
    Posts
    29
    Quote Originally Posted by masterxfile View Post
    Thank you snoopfrogg,

    You were right I had to create a new node.

    Code:
    #include <stdio.h>#include <stdlib.h>
    struct Node {
      int val;
      struct Node *left, *right;
    };
    
    void bstSort(int *arr, int n);
    struct Node *insert(struct Node *n, int val);
    void storeSorted(struct Node *n, int *arr, int *pos);
    void bstDestroy(struct Node *n);
    
    int main()
    {
      int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
      int n = sizeof(arr) / sizeof(arr[0]);
    
      bstSort(&arr, n);
    
      for (int ii = 0; ii < n; ii++)
        printf("%d\n", arr[ii]);
    
      getchar();
      return 0;
    }
    
    void bstSort(int *arr, int n)
    {
      struct Node *root = NULL;
    
      // root = insert(root, arr[0]);
    
      for (int i = 0; i < n; i++)
        insert(root, arr[i]);
    
      storeSorted(root, arr, &arr[0]);
      bstDestroy(root);
    }
    
    struct Node *insert(struct Node *n, int val)
    {
      if (n == NULL) {
        n = malloc(sizeof(struct Node));
        (n)->left = NULL;
        (n)->val = val;
        (n)->right = NULL;
      } else {
        if (val < n->val)
          n->left = insert(n->left, val);
        else if (val > n->val)
          n->right = insert(n->right, val);
      }
    
      return n;
    }
    
    void storeSorted(struct Node *n, int *arr, int *pos)
    {
      if (n != NULL) {
        storeSorted(n->left, arr, pos);
        arr[*pos] = n->val;
        storeSorted(n->right, arr, pos);
    
      }
    }
    
    void bstDestroy(struct Node *n)
    {
      if (n == NULL)
        return;
      if (n->left != NULL)
        bstDestroy(n->left);
      if (n->right != NULL)
        bstDestroy(n->right);
      free(n);
      return;
    }
    Now I have only one problem left.
    The code above works and it creates the tree structure as needed, the only thing is that in the storeSorted function the array is sorted but it remains there.

    When I go back to the top of the code it is not sorted so I might need to do some more research.

    1. You don't need the for loop or getchar() in your main function.
    2. Your bstSort function is incorrect.
    3. You don't increment the position of the array when storing the inorder traversal in arr
    4. You don't print out the inorder values of the BST in your bstDestroy function and you don't need the return statement.
    5. You don't insert the new node properly in your insert function.


    Try something like this:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
      int val;
      struct Node *left, *right;
    };
     
    void bstSort(int *arr, int n);
    struct Node *insert(struct Node *n, int val);
    void storeSorted(struct Node *n, int *arr, int *pos);
    void bstDestroy(struct Node *n);
     
    int main()
    {
    
      int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
      int n = sizeof(arr) / sizeof(arr[0]);
     
      bstSort(&arr, n);
      return 0;
    }
     
    void bstSort(int *arr, int n)
    {
      struct Node *root = NULL;
      
      root = insert(root, arr[0]);
     
      for (int i = 1; i < n; i++)
        insert(root, arr[i]);
      
      int i = 0;  
      storeSorted(root, arr, n);
      printf("BST is as follows: ");
      bstDestroy(root);
    }
     
    struct Node *insert(struct Node *n, int val)
    {
      if (n == NULL) {
          // perform binary tree insertion
        struct Node *n = (struct Node*)malloc(sizeof(struct Node));
        n->val = val;
        n->left = NULL;
        n->right = NULL;
        return n;
    
      } 
      // right insertion
      if(val > (n->val)){
        n->right = insert(n->right, val);
      }
      // left insertion
      else{
        n->left = insert(n->left, val);
      }
      return n;
    }
     
    void storeSorted(struct Node *n, int *arr, int *pos)
    {
      int i = pos++;
      if (n != NULL) {
        storeSorted(n->left, arr, i);
        arr[i] = n->val;
        storeSorted(n->right, arr, i);
     
      }
    }
     
    void bstDestroy(struct Node *n)
    {
      if (n != NULL){
        bstDestroy(n->left);
        printf("%d ", n->val);
        bstDestroy(n->right);
      }
      free(n);
    }
    "One of the best programming skills you can have is knowing when to walk away for awhile."

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,158
    Quote Originally Posted by masterxfile
    Code:
    bstSort(&arr, n);
    When passed as an argument, an array is converted to a pointer to its first element. Therefore, you should have written:
    Code:
    bstSort(arr, n);
    &arr actually results in a pointer to the entire array, i.e., int(*)[8] instead of int*

    Quote Originally Posted by snoopfrogg
    You don't need the for loop or getchar() in your main function.
    While it is true that getchar() is unnecessary, the for loop is a perfectly fine way to print the elements of the array so as to show they have been sorted.

    Quote Originally Posted by snoopfrogg
    You don't print out the inorder values of the BST in your bstDestroy function
    That's perfectly fine. The purpose of bstDestroy is to clean up the resources used to create the binary search tree, not to print anything. In fact, it is a rather bad habit to try and print from such a function: if you wanted to print a binary tree with in-order traversal, then write a function for that purpose rather than piggyback on a function with an entirely different purpose (i.e., functions should do one thing and do it well). But that would be unnecessary too (and against the instructions): the right place to print is after calling bstSort, to demonstrate that the array has been sorted.

    Quote Originally Posted by snoopfrogg
    Code:
    struct Node *n = (struct Node*)malloc(sizeof(struct Node));
    It is not necessary to cast the return value of malloc, and since there is a parameter named n, it is not a good idea to have another variable named n hide that existing variable in an inner scope. masterxfile's code is better in this regard.

    It is also generally good practice to check that malloc did not return a null pointer.
    Last edited by laserlight; 04-09-2019 at 11:54 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Apr 2019
    Posts
    10
    Quote Originally Posted by snoopfrogg View Post
    Try something like this:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
      int val;
      struct Node *left, *right;
    };
     
    void bstSort(int *arr, int n);
    struct Node *insert(struct Node *n, int val);
    void storeSorted(struct Node *n, int *arr, int *pos);
    void bstDestroy(struct Node *n);
     
    int main()
    {
    
      int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
      int n = sizeof(arr) / sizeof(arr[0]);
     
      bstSort(&arr, n);
      return 0;
    }
     
    void bstSort(int *arr, int n)
    {
      struct Node *root = NULL;
      
      root = insert(root, arr[0]);
     
      for (int i = 1; i < n; i++)
        insert(root, arr[i]);
      
      int i = 0;  
      storeSorted(root, arr, n);
      printf("BST is as follows: ");
      bstDestroy(root);
    }
     
    struct Node *insert(struct Node *n, int val)
    {
      if (n == NULL) {
          // perform binary tree insertion
        struct Node *n = (struct Node*)malloc(sizeof(struct Node));
        n->val = val;
        n->left = NULL;
        n->right = NULL;
        return n;
    
      } 
      // right insertion
      if(val > (n->val)){
        n->right = insert(n->right, val);
      }
      // left insertion
      else{
        n->left = insert(n->left, val);
      }
      return n;
    }
     
    void storeSorted(struct Node *n, int *arr, int *pos)
    {
      int i = pos++;
      if (n != NULL) {
        storeSorted(n->left, arr, i);
        arr[i] = n->val;
        storeSorted(n->right, arr, i);
     
      }
    }
     
    void bstDestroy(struct Node *n)
    {
      if (n != NULL){
        bstDestroy(n->left);
        printf("%d ", n->val);
        bstDestroy(n->right);
      }
      free(n);
    }
    Your code works perfectly except one problem, the array is not getting sorted in the storeSorted function.

    I have tried different options but all give the same result. If you print back the array you will see all messed up data. Any ideea?

    I did a print to test and the result is below:

    value in n 5 - OK
    value in pointer 5 - OK
    value of pointer 0 - OK
    value in n 8 - OK
    value in pointer 8 - OK
    value of pointer 1 - OK
    value in n 9 - OK
    value in pointer 9 - OK
    value of pointer 2 - OK
    value in n 10 - OK
    value in pointer 10 - OK
    value of pointer 0 - Wrong
    value in n 16 - OK
    value in pointer 16 - OK
    value of pointer 1- Wrong
    value in n 20 - OK
    value in pointer 20 - OK
    value of pointer 1- Wrong
    value in n 50 - OK
    value in pointer 50 - OK
    value of pointer 2- Wrong
    value in n 70 - OK
    value in pointer 70 - OK
    value of pointer 2- Wrong

    As you can see at some point the pointer goes back to zero and is replacing the values inside. This drives me crazy

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,158
    It should have been:
    Code:
    void storeSorted(struct Node *n, int *arr, int *pos)
    {
      if (n) {
        storeSorted(n->left, arr, pos);
        arr[(*pos)++] = n->val;
        storeSorted(n->right, arr, pos);
      }
    }
    Also, the current position was correctly declared in bstSort, but unused, so you need to fix that too. I would rename it pos instead of i.

    Pay attention to the compiler warnings.
    Last edited by laserlight; 04-10-2019 at 09:44 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Code:
    struct Node *insert(struct Node *n, int val)
    {
      if (n == NULL) {
          // perform binary tree insertion
        struct Node *n = (struct Node*)malloc(sizeof(struct Node));
        n->val = val;
        n->left = NULL;
        n->right = NULL;
        return n;
        ...
    I think that what you are trying to do is...
    Code:
    if (n == NULL) {
        // perform binary tree insertion
        /* You want a new node, not "n" as n is an argument to the function */
        struct Node *newNode = malloc(sizeof(*newNode)); 
        /* Test for fail */
        if (*newNode  != NULL) {
          newNode ->val = val;
          newNode ->left = NULL;
          newNode ->right = NULL;
        }
        /* Will return NULL if failed */
        return newNode;
        ...
    I've removed the cast from your malloc, as it is not needed and can hide if you've forgotten stdlib.h

    Casting malloc - Cprogramming.com

    You also need to handle if val == n->val. Do you really want to insert a duplicate?
    Fact - Beethoven wrote his first symphony in C

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,158
    Click_here: you're supposed to check if newNode is a null pointer, not if *newNode is a null pointer

    The reuse of the formal argument n is arguably okay (yes, pun), but what snoopfrogg did was to create a new variable named n in an inner scope, hence shadowing the parameter.

    Quote Originally Posted by Click_here
    You also need to handle if val == n->val. Do you really want to insert a duplicate?
    masterxfile's code didn't handle that, but that's handled by snoopfrogg's fix. If duplicates are allowed in the array, then surely they are allowed in the binary search tree.
    Last edited by laserlight; 04-10-2019 at 05:31 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Whoops - I'm just being lazy and not running the code before posting.

  15. #15
    Registered User
    Join Date
    Apr 2019
    Posts
    10
    I solved the problem, now all the functions are working properly.

    All I had to do is create a pointer to 0 and call the function using it, then increment that pointer each time I am storing a value in the array.
    Code:
        if (n != NULL) {
            storeSorted(n->left, arr, pos);
            arr[(*pos)++] = n->val;
            storeSorted(n->right, arr, pos);
    }
    
    Thank you all for the tips.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree sort
    By ElPosto in forum C Programming
    Replies: 27
    Last Post: 01-03-2018, 02:26 AM
  2. Replies: 9
    Last Post: 02-11-2013, 04:01 AM
  3. Need help with tree sort in C
    By jimjones371 in forum C Programming
    Replies: 1
    Last Post: 04-30-2012, 04:57 PM
  4. Binary sort number arranging tree
    By newtocpp in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 05:19 AM
  5. Binary Tree Sort
    By BakAttack in forum C++ Programming
    Replies: 6
    Last Post: 02-06-2003, 12:07 PM

Tags for this Thread