Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Finding the height of a binary tree in C, C++ | FACE Prep

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.


height of a binary tree


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


Algorithm to find the height of a binary tree using recursion


  1. If the binary tree is empty, then return 0.
  2. 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.


Program to find the height of a binary tree using recursion


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)


Algorithm to find the height of a binary tree using iterative method


  1. Create a queue and push the root node to the queue.
  2. Initialize height = 0.
  3. Repeat while there are elements in the queue.
  4. Initialize node_count = size of the queue
  5. While(node_count > 0)
  6. Pop nodes from the queue
  7. Push its children to the queue
  8. Decrement node_count
  9. If (node_count == 0)
  10. Return height
  11. Else
  12. Increment height


C++ Program to find the height of the binary tree using iterative method


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