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.

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;
        }
}

---

Quote:

---

Originally Posted by Salem

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.

You have N nodes in the tree, how many do you visit?

Quote:

---

Originally Posted by Salem

You have N nodes in the tree, how many do you visit?

---

So the time complexity will be O(n)?

Yes.