How to get the size of a binary tree ?
- by Andrei Ciobanu
I have a very simple binary tree structure, something like:
struct nmbintree_s {
unsigned int size;
int (*cmp)(const void *e1, const void *e2);
void (*destructor)(void *data);
nmbintree_node *root;
};
struct nmbintree_node_s {
void *data;
struct nmbintree_node_s *right;
struct nmbintree_node_s *left;
};
Sometimes i need to extract a 'tree' from another and i need to get the size to the 'extracted tree' in order to update the size of the initial 'tree' .
I was thinking on two approaches:
1) Using a recursive function, something like:
unsigned int nmbintree_size(struct nmbintree_node* node) {
if (node==NULL) {
return(0);
}
return( nmbintree_size(node->left) + nmbintree_size(node->right) + 1 );
}
2) A preorder / inorder / postorder traversal done in an iterative way (using stack / queue) + counting the nodes.
What approach do you think is more 'memory failure proof' / performant ?
Any other suggestions / tips ?
NOTE: I am probably going to use this implementation in the future for small projects of mine. So I don't want to unexpectedly fail :).
