Monday, July 13, 2015

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)

No comments:

Post a Comment