DAA: Find the Height or Maximum Depth of a Binary Tree

Find the Height or Maximum Depth of a Binary Tree

We have a binary tree structure and we need to find its height. It is defined by the distance from the root to the last downward node.

Here the height is 2.

Lets understand it with another example:

The height of the above tree is 3.

Approach

Recursively find the height of the left and right subtrees, and a maximum of two will be the height of the tree.

Pseudo code

1. If tree == NULL then, return 0

2. Else

            (a) call maxDepth( tree->left-subtree) recursively.

            (a) call maxDepth( tree->right-subtree) recursively.

            (c) After we get maximum depths -

            max_depth = max(max dept of left subtree,  max depth of right subtree) + 1

            (d) Return max_depth as height of tree.

C++ Code:

 #include <bits/stdc++.h>
 using namespace std;
 // Create tree structure
 class node {
 public:
     int data; // value of a node
     node* left; // left pointer to the tree
     node* right; // right pointer to the tree
 };
 // function to find the Height of the tree
 int maxDepth(node* node)
 {
     if (node == NULL) // if we reach root node
         return 0;
     else {
         int lDepth = maxDepth(node->left); // find height of left subtree
         int rDepth = maxDepth(node->right); // find height of the right subtree
         // return the largest one
         if (lDepth > rDepth)
             return (lDepth + 1); // if left subtree height is greater return its height + 1
         else
             return (rDepth + 1); // if right subtree height is greater return its height + 1
     }
 }
 // A function to insert data in to the tree
 node* newNode(int data)
 {
     node* Node = new node(); // Allocate memory for node
     Node->data = data; // Assign value to the tree
     Node->left = NULL; // Make left pointer NULL
     Node->right = NULL; // Make right pointer NULL
     return (Node); // return that Node
 }
 // Main function
 int main()
 {
     node* root = newNode(1); // root of the tree
     root->left = newNode(2); // the left of root
     root->right = newNode(3); // the right of root
     cout << "Height of tree is " << maxDepth(root); // call function to find Height
     return 0;
 } 

C Code:

 #include <stdio.h>
 #include <stdlib.h>
 // Create tree structure
 struct node {
     int data; // the data to the node
     struct node* left; // the left pointer to the node
     struct node* right; // the right pointer to the node
 };
 int maxDepth(struct node* node) // function to find the Height of the tree
 {
     if (node == NULL) // if we reach root node
         return 0;
     else {
         int lDepth = maxDepth(node->left); // find height of left subtree
         int rDepth = maxDepth(node->right); // find height of the right subtree
         // return the largest one
         if (lDepth > rDepth)
             return (lDepth + 1); // In case left subtree is greater
         else
             return (rDepth + 1); // In case right subtree is greater
     }
 }
 // Allocate memory to the node
 struct node* newNode(int data)
 {
     struct node* node  = (struct node*)malloc(sizeof(struct node));
     node->data = data; // assign data
     node->left = NULL; // the left pointer is NULL
     node->right = NULL; // the right pointer is NULL
     return (node); // return current node
 }
 // Main function
 int main()
 {
     struct node* root = newNode(1); // create root node
     root->left = newNode(2); // create left child
     root->right = newNode(3); // create right child
     printf("Height of tree is %d", maxDepth(root)); // find height of the tree
        return 0;
 } 

Output:

Height of tree is 2

Time complexity:

O(n)