Every node in a binary tree can be considered belonging to a column. If we assume that 'root' belongs to column '0' then root->left belongs to column '-1', root->right belongs to column '+1' and root->left->right belongs to column '0' and so on. We have to find the total number of such columns.
void totalCol(struct node* root, int col, int* minC, int* maxC)
{
if(root == NULL)
return;
totalCol(root->left, col-1, minC, maxC);
totalCol(root->right, col+1, minC, maxC);
*minC = MIN(*minC, col);
*maxC = MAX(*maxC, col);
}
int main()
{
struct node *root=NULL;
int minC=0;
int maxC=0;
insert(&root, 50);
insert(&root, 25);
insert(&root, 100);
insert(&root, 30);
insert(&root, 10);
insert(&root, 5);
totalCol(root, 0, &minC, &maxC);
printf("Total Col: %d\n", maxC - minC + 1);
return 0;
}
No comments:
Post a Comment