Link copied to clipboard. Share away!

Dismiss

Published on 09 Mar 2020

Program to find the height of a binary tree is discussed here. The height of a binary tree is nothing but the distance between the root node (first node) and the leaf node (last node). A binary tree has two subtrees: Left subtree and right subtree. The challenge here is to find out in which subtree is the leaf node present.

So, to find this out, we first calculate the height of the left subtree. Second, we calculate the height of the right subtree by traversing through it. Now, we find the maximum of these two heights and add 1 to it (1 is added as the root node should also be included in calculating the length). This gives us the height/depth of the binary tree.

Let us now look at an example. Below is the binary tree for which height needs to be calculated.

The height of right subtree = 4 {10, 5, 22, 7}

The height of left subtree = 3 {1, 4, 8}

Maximum (Height of right subtree, Height of left subtree) = Max (4, 3) = 4

Height of the tree = 4 + 1 (root) = 5

- If the binary tree is empty, then return 0.
- Else

- Get the maximum height of the left subtree recursively. Function height_of_binary_tree (tree->left-subtree)
- Get the maximum height of the right subtree recursively. height_of_binary_tree (tree->right-subtree)
- Get the max of maximum heights of left and right subtrees. Add 1 to it for the current node.
- max_height = max(max_height of left subtree, maximum_height of right subtree) + 1
- Return maximum_height.

C

C++

Output

Input-
3
1 2 1
2 3 1
3 4 1
4 3 2 1
Output-
Height of binary tree :4

**Time complexity: **O(n)

- Create a queue and push the root node to the queue.
- Initialize height = 0.
- Repeat while there are elements in the queue.
- Initialize node_count = size of the queue
- While(node_count > 0)
- Pop nodes from the queue
- Push its children to the queue
- Decrement node_count
- If (node_count == 0)
- Return height
- Else
- Increment height

C++

Output

Input-
3
1 2 1
2 3 1
3 4 1
4 3 2 1
Output-
Height of binary tree:4

**Time complexity:** O(n)

*Recommended Programs*

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×