{"id":1679,"date":"2020-06-11T11:06:25","date_gmt":"2020-06-11T11:06:25","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1679"},"modified":"2022-03-23T23:09:25","modified_gmt":"2022-03-23T23:09:25","slug":"height-of-tree","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/height-of-tree\/","title":{"rendered":"Height of Tree"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

BFS , Recursion<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a binary tree, our task is to print the height of the tree. Consider root node height as 1.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Method 1 (Using Queue) :<\/h3>\n
\n

We will use queue To store the height. Height is the maximum number of the levels we could traverse. In this approach we will store the root into the queue. Now we will perform bfs<\/strong> or level order traversal<\/strong> and increment the height by 1<\/code> with every level. <\/p>\n

See C++ implementation.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Method 2 (Using Recursion) :<\/h3>\n
\n

We will use recursion<\/strong> to traverse the nodes of our tree<\/strong> in post order fashion.<\/p>\n

Our program should consider number of nodes in the longest path.<\/p>\n

We will calculate the height of the left<\/strong> & right<\/strong> subtree. The height of the tree at any point is equal to the maximum height of it left<\/strong> & right<\/strong> subtree plus 1<\/code>.<\/p>\n

Below is the implementation in three different languages.<\/p>\n<\/blockquote>\n

Complexity Analysis:<\/h3>\n
\n

Time complexity<\/strong> of the method 1 is O(n)<\/code>, where n<\/code> is the number of nodes.<\/p>\n

Space complexity<\/strong> of this method is O(n)<\/code>, for the queue to store n<\/code> nodes.<\/p>\n<\/blockquote>\n

SOLUTIONS:<\/h3>\n

\t\t\t\t\t\t