Write a Program to Find the Maximum Depth or Height of a Tree
Given a binary tree, find height of it. Height of empty tree is -1, height of tree with one node is 0 and height of below tree is 2.

Recursively calculate height of left and right subtrees of a node and
assign height to the node as max of the heights of two children plus 1.
See below pseudo code and program for details.
Algorithm:
maxDepth()
1. If tree is empty then return -1
2. Else
(a) Get the max depth of left subtree recursively i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depthSee the below diagram for more clarity about execution of the recursive function maxDepth() for above example tree.
maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1
= 1 + 1
/ \
/ \
/ \
/ \
/ \
maxDepth('2') = 1 maxDepth('3') = 0
= max(maxDepth('4'), maxDepth('5')) + 1
= 1 + 0 = 1
/ \
/ \
/ \
/ \
/ \
maxDepth('4') = 0 maxDepth('5') = 0Implementation:
Height of tree is 2
Time Complexity: O(n) (Please see our post Tree Traversal for details)
Auxiliary Space: O(n) due to recursive calls.
Method 2: Another method to solve this problem is to do Level Order Traversal. While doing the level order traversal, while adding Nodes at each level to Queue, we have to add NULL Node so that whenever it is encountered, we can increment the value of variable and that level get counted.
Implementation:
#include <iostream>#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node{ int key; struct Node* left, *right;}; // Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);} /*Function to find the height(depth) of the tree*/int height(struct Node* root){ //Initialising a variable to count the //height of tree int depth = 0; queue<Node*>q; //Pushing first level element along with NULL q.push(root); q.push(NULL); while(!q.empty()){ Node* temp = q.front(); q.pop(); //When NULL encountered, increment the value if(temp == NULL){ depth++; } //If NULL not encountered, keep moving if(temp != NULL){ if(temp->left){ q.push(temp->left); } if(temp->right){ q.push(temp->right); } } //If queue still have elements left, //push NULL again to the queue. else if(!q.empty()){ q.push(NULL); } } return depth;}// Driver programint main(){ // Let us create Binary Tree shown in above example Node *root = newNode(1); root->left = newNode(12); root->right = newNode(13); root->right->left = newNode(14); root->right->right = newNode(15); root->right->left->left = newNode(21); root->right->left->right = newNode(22); root->right->right->left = newNode(23); root->right->right->right = newNode(24); cout<<"Height(Depth) of tree is: "<<height(root);} |
Height(Depth) of tree is: 4
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3: This method also uses the concept of Level Order Traversal but we wont be adding null in the Queue. We will simply increase the counter when the level will increase and then remove all the nodes from the queue of the current Level.
// Java program for above approachimport java.util.LinkedList;import java.util.Queue;class GFG {// A tree node structurestatic class Node { int key; Node left; Node right;}// Utility function to create// a new nodestatic Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return temp;}/*Function to find the height(depth) of the tree*/public static int height( Node root){ //Initialising a variable to count the //height of tree Queue<Node>q=new LinkedList<Node>(); q.add(root); int height=0; while(!q.isEmpty()){ int size=q.size(); for(int i=0;i<size;i++){ Node temp=q.poll(); if(temp.left!=null){ q.add(temp.left); } if(temp.right!=null){ q.add(temp.right); } } height++; } return height;}// Driver Codepublic static void main(String args[]) { Node root = newNode(1); root.left = newNode(12); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(23); root.right.right.right = newNode(24); System.out.println("Height(Depth) of tree is: "+height(root)); }} |
Height(Depth) of tree is: 4
Time Complexity: O(n)
Auxiliary Space: O(n)
