C-Question Binary Tree Implementation Found in K & R

Question

So, I read the K & RC book and ask a question .. in the 6th chapter on structures on pages 140-141, there is a code that looks like this (I took out some of the more non-local parts)

/* the program loops through a tree looking for some word if it finds the word itll incremenet the count by 1 if it doesnt itll add a new node */ struct node { char *word; int count; struct node *left; struct node *right; } main() { struct node *root; char word[1000]; root = NULL; while(getword(word, MAXWORD) != EOF) /* getword just grabs 1 word at a time from a file of words */ if(isalpha(word[0])) /* isalpha checks to see if it is a valid word */ root = addNode(root, word); treeprint(root); /* prints the tree */ return 0; } struct node *addNode(struct node *p, char *w) { int cond; if(p == NULL) { p = malloc(sizeof(struct node)); /* allocates memory for the new node */ p -> word = strdup(w); p -> count = 1; p -> left = p -> right = NULL; } else if ((cond = strcmp(w, p -> word)) == 0) p -> count++; else if(cond < 0) p -> left = addNode(p -> left, w); else p -> right = addNode(p -> right, w); return p; } 

And my confusion in the main () function in the root = addNode (root, word)

If addNode returns a pointer to a newly added node (or to a node if it already has an int he tree), has this not "lost" all the data above the tree? Shouldn't the root remain the root of the tree?

Thanks!

Answer 1

root always remains as the root of the tree. root is passed as the first addNode parameter, which will only be malloc if it is NULL , i.e. when root is passed for the first time. In subsequent calls, it will not change root , it will only change count , left or right . Note that in the recursive addNode p calls are not passed, but the left or right child is passed. Try to go through a tree with paper and a pencil / pen, and you will understand how the nodes are added.

Answer 2

Your misunderstanding about addNode behavior. It does not return a pointer to a newly added node; rather, it returns a pointer to the node that was passed, p (unless it was NULL ).

Since the only time that root == NULL is when the very first word is added, root will have the same value from this point, and get that same value again and again. This is just an elegant way to deal with empty trees that are represented by a NULL pointer.

Remember that each recursive call to addNode has a different value for p . This is how local variables work; they are local to a particular function call, and not to the function as a whole. Perhaps this led to a misunderstanding of the behavior of the function.