Find height of a binary tree

lazylibran82 0 Tallied Votes 167 Views Share

This code enables one to find the height of a binary tree using a queue and a marker.

// 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.