Thread: total nodes in a tree

  1. #1
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804

    total nodes in a tree

    I made a code to count the total number of nodes in a binary tree.
    Code:
    int count(struct node *root)
    {
    	static int i=0;
    	if(root!=NULL)
    	{
    		count(root->left);
    		i++;
    		count(root->right);
    	}
    	return i;
    }
    It simply traverses the tree using inorder traversal and counts all the nodes.
    I also found a code somewhere which is like this:
    Code:
    int tree_size(struct node* node)
    {
    if (node==NULL)
    {
    return(0);
    }
    else
    {
    return(tree_size(node->left) + tree_size(node->right) + 1);
    }
    }
    I want to know which one will be more efficent(time and space). What is the "O" notation for both of the codes?
    I'm a little weak to find "O" notation, that's why I'm asking for it.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You're using a static local variable, which is 1-time initialised to 0.
    What happens if you call the function again?

    Code:
    int count(struct node *root)
    {
    	if(root!=NULL)
    	{
    		return 1 + count(root->left) + count(root->right);
    	}
    	else {
    		return 0;
    	}
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by Salem View Post
    You're using a static local variable, which is 1-time initialised to 0.
    What happens if you call the function again?

    Code:
    int count(struct node *root)
    {
    	if(root!=NULL)
    	{
    		return 1 + count(root->left) + count(root->right);
    	}
    	else {
    		return 0;
    	}
    }
    Oh, now I think I got the mistake in my code using static variable. Thanks.
    But can you tell me how to compute "O" for the code given by you. Also frankly speaking I'm getting problem in tracing these tough recursive routines as I'm not able to do them by pencil paper coz there are several returning points. Somebody please help me to solve these recursive methods.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You have N nodes in the tree, how many do you visit?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by Salem View Post
    You have N nodes in the tree, how many do you visit?
    So the time complexity will be O(n)?
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Yes.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  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