Function to find Height of Binary Tree

we can calculate Height of binary tree using recursion and without recursion also.

1.recursive Method: get the height of left subTree and right subTree then return the max(hightOfLeftSubTree,heightOfRightSubTree)+1.

//calculate height of tree using recursion
static int heightOfBinaryTree(treeNode *rootNode) {

	if (rootNode == NULL)
		return 0;
	else {
		//get the height of left child
		int leftHeight = tree::heightOfBinaryTree(rootNode->leftChild);

		//get the height of right child
		int rightHeight = tree::heightOfBinaryTree(rootNode->rightChild);

		//return max(leftHeight,rightHeight)+1
		if (leftHeight > rightHeight)
			return leftHeight + 1;
		else
			return rightHeight + 1;
	}

}

2. Non-recursive Method: create two queues which store current level and next level nodes.when we move from one level to another then increase height variable.

//calculate height of tree without recursion
static int heightOfBinaryTreeWithoutRecursion(treeNode *rootNode) {
	int height = 0;
	//create queues to store current and next level nodes
	queue<treeNode*> Q1;
	queue<treeNode*> Q2;

	//add top rootNode to Q1
	Q1.push(rootNode);

	while (!Q1.empty()) { //for each level
		treeNode * temp = Q1.front();
		Q1.pop();

		if (temp->leftChild)
			Q2.push(temp->leftChild);

		if (temp->rightChild)
			Q2.push(temp->rightChild);

		if (Q1.empty()) {
			//increase height when move to another level
			height++;
			//swap elements from next level to current level
			swap(Q1, Q2);
		}
	}
	return height; //final height of tree
}

above mention function is member function of my Tree ADT class you can check complete program here

A Developer
Gy@n!