0

I have been writing a program that is supposed to determine how long that the process has taken, however, it fails and always returns a value of 0.0000 seconds. 

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <time.h>

struct node
{
        int data;
        struct node *left;
        struct node *right;
};
struct node *tree;
struct node *InsertElement(struct node *, int); //declaration//
struct node *findLargestElement(struct node *);
void create_tree(struct node *);

void create_tree(struct node *tree)
{
        tree=NULL;  //resets the tree//
}

struct node *findLargestElement(struct node *tree)
{
    if((tree==NULL)|| (tree->right==NULL))
        return tree;
    else
        return findLargestElement(tree->right);
}

   struct node *InsertElement(struct node *tree, int val)
{
    struct node *ptr, *nodeptr, *parentptr;
    ptr = (struct node*)malloc(sizeof(struct node)); //memory allocation//
    ptr->data = val;
    ptr->left = NULL;
    ptr->right = NULL;
    if(tree==NULL) //for root node//
    {
        tree=ptr;
        tree->left=NULL;
        tree->right=NULL;
    }
    else
    {
        parentptr=NULL;
        nodeptr=tree;
        while(nodeptr!=NULL)
        {
        parentptr=nodeptr;
        if(val<nodeptr->data)
        nodeptr=nodeptr->left; //if value is less than root go left//
        else
        nodeptr = nodeptr->right;//if more go right//
        }
        if(val<parentptr->data)//if less than parent go left//
        parentptr->left = ptr;
        else
        parentptr->right = ptr;
    }
    return tree;
}

int main()
{
    int option, val;
    struct node *ptr;
    clock_t begin, end;
    create_tree(tree);

         do
    {
        printf("\n\n\n\t\t*****Main Menu****\n\n");
        printf("\t\t 1. Add new nodes: \n");
        printf("\t\t 2. Find the largest element\n");
        printf("\t\t 11. Exit\n");
        printf("Enter your option : ");
        scanf("%d", &option);

        switch(option)
        {
            case 1:   printf("\nEnter the value of the new node:");
                        scanf("%d", &val);
                        tree= InsertElement(tree,val);
                        break;

            case 2:     begin=clock();  //timer begin//
                        ptr = findLargestElement(tree);
                        end=clock();   //timer ends//
                        double time_spent=(double)(end-begin)/CLOCKS_PER_SEC; //time elapsed//
                        printf("\nThe largest element is:%d\n", ptr->data);
                        printf("The  time taken is %f  end time is", time_spent);
                        break;

        }
    }while(option!=11);

    return 0;
}

This is part of a program which will find the largest value in a binary search tree. (EDIT: I have added additional code for clarification. This program would have the user input the nodes for the tree and then rearrange the nodes accordingly, there is theoretically no limit for a number of nodes. My main question is once again is my implementation of the timer is correct? or is there another way to do it?) This is just part of the code that I have written and I would like to know whether there are any alternatives to time the process has taken or did I code it wrongly. I would like the time taken to be the elapsed time. Is this method only viable for loops only?

I have tried something like

begin=clock();
ptr = findLargestElement(tree);
end=clock();
printf("The  start time %f and the end time is %f", begin,end)

it returns a start time of 0 and a large number as the end time, however converting it to seconds does not seem to work for me.

(Additional info: I have gone through the time.h documentation and it seems like the clock() should work, I have been trying other methods mentioned on StackOverflow but none of them seem to be working. Is it because I use a struct instead?) Thanks

JakeDan
  • 9
  • 3
  • 1
    Unrelated to your problem, but you should get into the habit of using *trailing* newlines in your `printf` calls. Two reasons: First the last output of the program won't then run into the command-line prompt (if running in a terminal). Secondly, output to `stdout` (which `printf` writes to) is by default *line-buffered*. That means output will be written on the newline, so a leading newline will print the *previous* output, but not the current. In some situation that might make it seem like output you expect isn't printed (it is, it's just waiting in a buffer). – Some programmer dude Dec 01 '18 at 10:07
  • 2
    As for your problem, please try to create a [mcve] to show us. Are you sure there are nodes in the tree? What is `tree`? How is `tree` declared and initialized? How is your tree created? How is `create_tree` declared and defined? How many nodes are supposed to be in the tree? – Some programmer dude Dec 01 '18 at 10:11
  • And remember that even though `clock` is a standard C function, it works differently on different platforms (on some (POSIX like Linux or macOS) it can be used to measure process CPU time, on others (like Windows) it can be used to measure wall-clock time). – Some programmer dude Dec 01 '18 at 10:12
  • Lastly, you might consider [learning how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). The code perhaps doesn't do what you think it's doing? – Some programmer dude Dec 01 '18 at 10:14
  • Hi thanks for your tips, I have edited the code so that it is complete and verifiable and added additional information. I have been debugging this program for some time but the implementation of time.h is a bit new to me and I have been searching around online but I don't see any one using time() for struct so I was wondering if I am on the correct path – JakeDan Dec 01 '18 at 11:46
  • `void create_tree(struct node *tree) { tree=NULL; //resets the tree// }` **<<--** this is the core of your misconceptions. – wildplasser Dec 01 '18 at 13:21
  • I understand that null can be considered a binary tree, I guess I should have clearer comments. Any idea about the timer? – JakeDan Dec 01 '18 at 14:50
  • https://stackoverflow.com/questions/1083142/what-s-the-correct-way-to-use-printf-to-print-a-clock-t – Doug Currie Dec 01 '18 at 16:46

2 Answers2

0

The type clock_t is not necessarily double -- it could be an integer type.

One approach is 

double begin = ((double )clock()) / CLOCKS_PER_SEC;
ptr = findLargestElement(tree);
double end = ((double )clock()) / CLOCKS_PER_SEC;
printf("The time taken is %f\n", end - begin);

Note that clock() is converted to double before the divide to preserve information in case clock_t is an integer type.

Doug Currie
  • 40,708
  • 1
  • 95
  • 119
  • I have tried this method and for me it still shows 0.000000. I tried debugging by printing the end and the begin separately, apparently both values are equal so when they minus out each other it will return a 0 value., – JakeDan Dec 02 '18 at 05:06
  • So, it is taking zero time in the resolution of the timer. In other words, it is starting and completing in the same clock() tick. Try putting a sleep() or another time wasting call in your function and see what happens. – Doug Currie Dec 02 '18 at 19:21
0

After searching and doing a lot of trial and error, I can conclude that the time taken is just too fast to be measured. During my testing phase, I had only a maximum of 50 nodes.

By referring to this website https://aaronjwood.com/articles/binary-search-trees/, I tweaked the code and the minimum amount of nodes that I needed to get a valid traversal time was 1,000,000 nodes.

So the conclusion can be, to solve this problem in C, we would have to use a large number of nodes.

JakeDan
  • 9
  • 3