recursive printf of binary tree elements

Question

I've come back to K&R in order to read one chapter, and noticed an example I had previously omitted. The chapter covers the topic of a binary tree data type. I understand storing new entries in the nodes, but printing function gives confuses me. Why is printing of the left part called first?

Would it work if printf would be the first command in function, followed by left and right?

If not - why then?

/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}

Answer 1

Descending the left side first, then printing the node itself, then descending the right side, is what makes this operation in-order tree traversal. If you moved the printf before the left descent, as you suggest, that would make it pre-order traversal. And if you did both descents first, that would be post-order. All three possibilities visit all of the nodes, but in three different orderings.

Consider the simple tree

  *
 / \
a   +
   / \
  b   c

If you traverse this tree in pre-order you get

* a + b c

In-order,

a * b + c

Post-order,

a b c + *

Which one of these possibilities you want depends on what you're doing.