Size of binary tree

Problem: Write a method which returns the number of nodes present in the given binary tree.

Solution: Do any traversal and instead of printing the node, count the number of nodes. I am using post order traversal here.

Implementation:

//Public Interface

int BSTree::size()

{

if(!root)

return 0;

return size(root);

}

//Actual Implementation

int BSTree::size(BSTree::Node *node)

{

if(!node)

return 0;

int ls = size(node->left);

int rs = size(node->right);

return ls + rs + 1;

} 

Complexity: O(n)