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.

Answer 2

Of course it would "work". You'd just get a different ordering on the output. You could also print the node after printing both child nodes. (And imagine if you had a tree with multiple children, not just two.)

The real question is whether the values of the tree nodes obey any special rules, and thus whether any particular traversal order is particularly meaningful. For example, for a binary search tree the left-self-right order prints out the values in sort order.

Answer 3

You can walk through a binary tree in different ways: Pre-order, In-order and Post-Order.

The printf could be an entirely different procedure (computation of node data). Some problems require different ways of walking on a tree, for example, if you're balancing a binary tree, you would calculate the balance factor after visiting both child trees.

So, the printf can be thought as a place holder for other kind of procedures/functions to deal with different kinds of problems.