Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Height of Tree

Last Updated on March 23, 2022 by Ria Pathak

BFS , Recursion

Easy

### Problem Statement :

Given a binary tree, our task is to print the height of the tree. Consider root node height as 1.

See original problem statement here

### Method 1 (Using Queue) :

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 or level order traversal and increment the height by `1` with every level.

See C++ implementation.

### Method 2 (Using Recursion) :

We will use recursion to traverse the nodes of our tree in post order fashion.

Our program should consider number of nodes in the longest path.

We will calculate the height of the left & right subtree. The height of the tree at any point is equal to the maximum height of it left & right subtree plus `1`.

Below is the implementation in three different languages.

### Complexity Analysis:

Time complexity of the method 1 is `O(n)`, where `n` is the number of nodes.

Space complexity of this method is `O(n)`, for the queue to store `n` nodes.

### SOLUTIONS:

```#include &lt;stdio.h&gt;

#include&lt;stdlib.h&gt;

#define ll long long

#define REP(i, n) for (i = 0; i &lt; n; i++)

struct nodelist

{

ll value;

struct nodelist *left;

struct nodelist *right;

};

typedef struct nodelist node;

struct Queue

{

int front, rear, size;

unsigned capacity;

node* *array;

};

typedef struct Queue queue;

queue* createQueue(unsigned capacity)

{

queue* qu =(queue*)malloc(sizeof(queue));

qu-&gt;capacity = capacity;

qu-&gt;front = qu-&gt;size =0;

qu-&gt;rear = capacity-1;

qu-&gt;array = (node **)malloc(qu-&gt;capacity * sizeof(node));

return qu;

}

int isFull(queue*  queue1)

{

return (queue1-&gt;size == queue1-&gt;capacity);

}

int isEmpty(queue* queue1)

{

return (queue1-&gt;size==0);

}

void enqueue(queue* queue1, node* item)

{

if(isFull(queue1))

return ;

queue1-&gt;rear = (queue1-&gt;rear +1 )%queue1-&gt;capacity;

queue1-&gt;array[queue1-&gt;rear] = item;

queue1-&gt;size = queue1-&gt;size +1;

}

node dequeue(queue* queue1)

{

node* item = queue1-&gt;array[queue1-&gt;front];

queue1-&gt;front = (queue1-&gt;front +1)%queue1-&gt;capacity;

queue1-&gt;size = queue1-&gt;size -1;

return *item;

}

node* front(queue* queue1)

{

return queue1-&gt;array[queue1-&gt;front];

}

node* rear(queue * queue1)

{

return queue1-&gt;array[queue1-&gt;rear];

}

node *createNode(ll value)

{

node *t= (node *) malloc(sizeof(node));

t-&gt;value = value;

t-&gt;right = t-&gt;left = NULL;

return  t;

}

void deleteNode(node*t)

{

free(t);

}

node *replaceNegativeOne(node *root)

{

if(root==NULL ||(root-&gt;value == -1 &amp;&amp; root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL))

return NULL;

root-&gt;left = replaceNegativeOne(root-&gt;left);

root-&gt;right = replaceNegativeOne(root-&gt;right);

return root;

}

void deleteTree(node *node1)

{

if(node1==NULL)

return;

deleteTree(node1-&gt;left);

deleteTree(node1-&gt;right);

free(node1);

}

node *createTreeByLevelTree()

{

ll n,m;

queue* queue1 = createQueue(100000);

node *root, *t;

root = NULL;

while(scanf("%lld", &amp;n))

{

if(isEmpty(queue1))

{

root= createNode(n);

enqueue(queue1,root);

continue;

}

scanf("%lld", &amp;m);

t = front(queue1);

dequeue(queue1);

t-&gt;left =createNode(n);

t-&gt;right=createNode(m);

if(t-&gt;left-&gt;value !=-1)

enqueue(queue1,t-&gt;left);

if(t-&gt;right-&gt;value !=-1)

enqueue(queue1,t-&gt;right);

if(isEmpty(queue1))

break;

}

return root;

}

int calculateHeight(node* n)

{

if(n ==NULL)

return 0;

int left = 1+calculateHeight(n-&gt;left);

int right = 1 + calculateHeight(n-&gt;right);

return (left&gt;right)?left:right;

}

int main() {

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

printf("%d\n", calculateHeight(root));

deleteTree(root);

return 0;

}
```
```#define REP(i, n) for (i = 0; i &lt; n; i++)

#define pb(a) push_back(a)

#define vi vector&lt;long&gt;

#define ll long long

#include &lt;bits/stdc++.h&gt;

using namespace std;

struct node

{

ll value;

node *left;

node *right;

};

node *createNode(ll value)

{

node *t = new node();

t-&gt;value = value;

t-&gt;right = t-&gt;left = NULL;

return t;

}

void deleteNode(node *t)

{

delete t;

}

node *replaceNegativeOne(node *root)

{

if (root == NULL || (root-&gt;value == -1 &amp;&amp; root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL))

return NULL;

root-&gt;left = replaceNegativeOne(root-&gt;left);

root-&gt;right = replaceNegativeOne(root-&gt;right);

return root;

}

node *createTreeByLevelTree()

{

ll n, m;

queue&lt;node *&gt; q;

node *root, *t;

root = NULL;

while (cin &gt;&gt; n)

{

if (q.empty())

{

root = createNode(n);

q.push(root);

continue;

}

cin &gt;&gt; m;

t = q.front();

q.pop();

t-&gt;left = createNode(n);

t-&gt;right = createNode(m);

if (t-&gt;left-&gt;value != -1)

{

q.push(t-&gt;left);

}

if (t-&gt;right-&gt;value != -1)

{

q.push(t-&gt;right);

}

if (q.empty())

{

break;

}

}

return root;

}

void deleteTree(node *node)

{

if (node == NULL)

return;

deleteTree(node-&gt;left);

deleteTree(node-&gt;right);

delete node;

}

int calculateHeight(node* root)

{

if (root == nullptr)

return 0;

queue&lt;node*&gt; queue;

queue.push(root);

node* front = nullptr;

int height = 0;

while (!queue.empty())

{

int size = queue.size();

while (size--)

{

front = queue.front();

queue.pop();

if (front-&gt;left)

queue.push(front-&gt;left);

if (front-&gt;right)

queue.push(front-&gt;right);

}

height++;

}

return height;

}

int main()

{

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

cout&lt;&lt; calculateHeight(root)&lt;&lt;endl;

deleteTree(root);

return 0;

}
```
```import java.util.LinkedList;

import java.util.*;

import java.util.Scanner;

import java.io.*;

class Node

{

long value;

Node left, right;

public Node(long item)

{

value = item;

left = right = null;

}

}

class BinaryTree {

Node root;

BinaryTree() {

root = null;

}

Node createNode(long value) {

Node t = new Node(value);

return t;

}

Node replaceNegativeOne(Node root) {

if (root == null || (root.value == -1 &amp;&amp; root.left == null &amp;&amp; root.right == null)) {

return null;

}

root.left = replaceNegativeOne(root.left);

root.right = replaceNegativeOne(root.right);

return root;

}

Node createTreeByLevelTree() {

Scanner sc = new Scanner(System.in);

long n, m;

Node t;

root = null;

while (sc.hasNext()) {

n = sc.nextLong();

if (queue.isEmpty()) {

root = createNode(n);

continue;

}

m = sc.nextLong();

t.left = createNode(n);

t.right = createNode(m);

if (t.left.value != -1)

if (t.right.value != -1)

if (queue.isEmpty())

break;

}

return root;

}

void deleteTree(Node node) {

node = null;

}

int calculateHeight(Node node) {

if(node == null)

return 0;

int left = 1+calculateHeight(node.left);

int right = 1 + calculateHeight(node.right);

return (left&gt;right)?left:right;

}

}

public class Main {

public static void main(String[] args) {

BinaryTree bt = new BinaryTree();

bt.root = bt.createTreeByLevelTree();

bt.root = bt.replaceNegativeOne(bt.root);

System.out.println(bt.calculateHeight(bt.root));

bt.deleteTree(bt.root);

}

}
```

[forminator_quiz id="1683"]

This article tried to discuss Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.