Question about computing the number of nodes in a Binary Tree

A Computer Science Professor at Stanford University used the following function to compute the number of nodes in a Binary Tree.

Code:

---

/*
 Compute the number of nodes in a tree.
*/
int size(struct node* node) {
  if (node==NULL) {
    return(0);
  } else {
    return(size(node->left) + 1 + size(node->right));
  }
}

Why use this method instead of doing something like a pre-order traversal?

---

Well whatever way its traversed the result should be the same. Also, they all have to check each node one by one, so they are all "equally fast", in terms of order of magnitude.

Quote:

---

Why use this method instead of doing something like a pre-order traversal?

---

You never said whether he/she said to use this one over a different method, so use whatever one you want! The only real difference is that this one uses recursion. Recursion has the overhead of making many function calls, so it might or might not be a little slower than say, an in-order (or other type of) traversal using an iterative approach.

You don't care about the order, so why bother going in order?


Quzah.

Perhaps you could show what code you were thinking of for a preorder traversal. One might consider this a preorder traversal:

Code:

---

int size(struct node* node) {
  if (node==NULL) {
    return(0);
  } else {
    return(1 + size(node->left) + size(node->right));
  }
}

---

Note the moving of the 1.