This code enables one to find the height of a binary tree using a queue and a marker.
Find height of a binary tree
// Height of a tree using a marker.
int height(node * tree)
{
node * tmp;
queue *qptr;
node * marker;
marker = (node*)malloc(sizeof(node));
marker->left = NULL;
marker->right = NULL;
marker->val = -111;
qptr = (queue*)malloc(sizeof(queue));
initialize(qptr);
int oneInsertion = -1;
int height = 0;
if(tree)
{
insert(tree,qptr);
insert(marker,qptr);
height++;
while(!emptyQ(qptr))
{
tmp = dele_te(qptr);
oneInsertion = -1;
while(tmp->val != marker->val)
{
// Make sure that atleast one insertion could be done.
// If inserting leaf node only, then do not insert the marker.
// This is the terminating condition for the marker insertion.
if(tmp->left || tmp->right || (tmp->left && tmp->right))
oneInsertion++;
if(tmp->left)
insert(tmp->left,qptr);
if(tmp->right)
insert(tmp->right,qptr);
tmp = dele_te(qptr);
}
if(oneInsertion > -1)
{
insert(marker,qptr);
height++;
}
}
return height;
}
else
{
printf("Tree is empty\n");
return height;
}
}
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.