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)