Thread: Question about computing the number of nodes in a Binary Tree

  1. #1
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329

    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?

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

    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.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You don't care about the order, so why bother going in order?


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree
    By Ideswa in forum C Programming
    Replies: 12
    Last Post: 10-25-2007, 12:24 PM
  2. adding a number to a number
    By bigmac(rexdale) in forum C Programming
    Replies: 11
    Last Post: 10-24-2007, 12:56 PM
  3. Need help with Binary Tree!!!
    By pityocamptes in forum C Programming
    Replies: 3
    Last Post: 04-17-2006, 10:27 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM