Height of Tree

Concepts Used

BFS , Recursion

Difficulty Level

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 refer some online programming courses and 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 <stdio.h>

#include<stdlib.h>

#define ll long long

#define REP(i, n) for (i = 0; i < 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->capacity = capacity;

    qu->front = qu->size =0;

    qu->rear = capacity-1;

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

    return qu;

}



int isFull(queue*  queue1)

{

    return (queue1->size == queue1->capacity);

}

int isEmpty(queue* queue1)

{

    return (queue1->size==0);

}



void enqueue(queue* queue1, node* item)

{

    if(isFull(queue1))

        return ;

    queue1->rear = (queue1->rear +1 )%queue1->capacity;

    queue1->array[queue1->rear] = item;

    queue1->size = queue1->size +1;



}



node dequeue(queue* queue1)

{

    node* item = queue1->array[queue1->front];

    queue1->front = (queue1->front +1)%queue1->capacity;

    queue1->size = queue1->size -1;

    return *item;

}



node* front(queue* queue1)

{

    return queue1->array[queue1->front];

}



node* rear(queue * queue1)

{

    return queue1->array[queue1->rear];

}

node *createNode(ll value)

{

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

    t->value = value;

    t->right = t->left = NULL;

    return  t;

}

void deleteNode(node*t)

{

    free(t);

}



node *replaceNegativeOne(node *root)

{

    if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



void deleteTree(node *node1)

{

    if(node1==NULL)

        return;

    deleteTree(node1->left);

    deleteTree(node1->right);

    free(node1);

}

node *createTreeByLevelTree()

{

    ll n,m;

    queue* queue1 = createQueue(100000);

    node *root, *t;

    root = NULL;

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

    {

        if(isEmpty(queue1))

        {

            root= createNode(n);

            enqueue(queue1,root);

            continue;

        }

        scanf("%lld", &m);

        t = front(queue1);

        dequeue(queue1);

        t->left =createNode(n);

        t->right=createNode(m);

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

            enqueue(queue1,t->left);

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

            enqueue(queue1,t->right);



        if(isEmpty(queue1))

            break;

    }

    return root;

}

int calculateHeight(node* n)

{

     if(n ==NULL)

     return 0;



    int left = 1+calculateHeight(n->left);

    int right = 1 + calculateHeight(n->right);



    return (left>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 < n; i++)

#define pb(a) push_back(a)

#define vi vector<long>

#define ll long long

#include <bits/stdc++.h>

using namespace std;

struct node

{

    ll value;

    node *left;

    node *right;

};



node *createNode(ll value)

{

    node *t = new node();

    t->value = value;

    t->right = t->left = NULL;

    return t;

}



void deleteNode(node *t)

{

    delete t;

}





node *replaceNegativeOne(node *root)

{

    if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



node *createTreeByLevelTree()

{

    ll n, m;

    queue<node *> q;



    node *root, *t;



    root = NULL;



    while (cin >> n)

    {

        if (q.empty())

        {

            root = createNode(n);

            q.push(root);

            continue;

        }

        cin >> m;



        t = q.front();

        q.pop();



        t->left = createNode(n);

        t->right = createNode(m);



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

        {

            q.push(t->left);

        }



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

        {

            q.push(t->right);

        }

          if (q.empty())

        {

            break;

        }

    }



    return root;

}



void deleteTree(node *node)

{

    if (node == NULL)

        return;



    deleteTree(node->left);

    deleteTree(node->right);

    delete node;

}

int calculateHeight(node* root)

{

    if (root == nullptr)

        return 0;



    queue<node*> 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->left)

                queue.push(front->left);



           if (front->right)

                queue.push(front->right);

        }



        height++;

    }



    return height;

}


int main()

{

    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    cout<< calculateHeight(root)<<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 && root.left == null && 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;

        Queue<Node> queue = new LinkedList<>();

        Node t;

        root = null;

        while (sc.hasNext()) {

            n = sc.nextLong();

            if (queue.isEmpty()) {

                root = createNode(n);

                ((LinkedList<Node>) queue).add(root);

                continue;

            }

            m = sc.nextLong();

            t = ((LinkedList<Node>) queue).peekFirst();

            ((LinkedList<Node>) queue).pop();

            t.left = createNode(n);

            t.right = createNode(m);

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

                ((LinkedList<Node>) queue).add(t.left);

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

                ((LinkedList<Node>) queue).add(t.right);

            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>right)?left:right;



}




}

public class Main {

    public static void main(String[] args) {

        // write your code here



            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);



    }

}

Previous post Maximum Distinct
Next post Inorder Traversal

Leave a Reply

Your email address will not be published. Required fields are marked *