Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Height of a Binary tree
3.
Algorithm
4.
Modified Height of a binary tree
5.
Depth of a node in a binary tree
6.
Frequently Asked Questions
6.1.
What is a binary search tree? 
6.2.
Is DFS & preorder traversal the same? 
7.
Conclusion
Last Updated: Mar 27, 2024

Height of a Binary Tree

Author ANKIT MITTAL
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A binary tree is an important data structure with applications in computer science, from operating systems to building servers. Using binary trees can reduce the complexity of various problems to a large extent. 

 

The depth of a tree node is equal to the number of edges from the node to the tree's root node. A root node has a depth of 0.

The height of a tree node is equal to the number of edges on the longest path from the node to a leaf. A leaf node has a height of 0.
 

In this blog, we will be covering a very common question on Binary trees: How can we calculate the height of a binary tree? 

Let’s understand it using an example.
 

Consider the binary tree given below:

binary tree

In the tree given above, 

Height - the height of a root node is 5 since the longest path from the root node to any of the leaf nodes is 5. 

Depth - the depth of the root node will be 0 since we are at the root node. 

The longest path is coloured, i.e. 1->2->4->6->7.

 

 The path for getting the height of the binary tree will be traversed as shown below : 

binary treebinary tree

 

 

binary treebinary tree

 

If we carefully try to observe the  depth and height of 2, then as per the definition 

Height - the height will be  4 (7->6->4->2)

Depth -  if we compute the depth then it will be 2 (1->2). 

 

Now, let’s understand the approach behind this.

Recommended: Try the Problem yourself before moving on to the solution

Height of a Binary tree

First, let us understand the concept of the height of a binary tree. The height of a binary tree is the maximum distance from the root node to any leaf node. First, let's discuss the recursive approach to calculating the height of a binary tree. 
 

  1. We will start from the root node and initially, the height will be 0. 
  2. We will recursively calculate the height of the left subtree. 
  3. Similarly, we will calculate the height of the right subtree. 
  4. Now I will calculate the height of the current node by adding 1 to the max height between the right and left subtree.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

We can solve this problem using a recursive algorithm which will be used to traverse the binary tree. This traversal is similar to depth-first search in the graph algorithm. Let us understand this algorithm with the help of the code given below:

#include<iostream>
 using namespace std; 
 
 struct Node {
     int val;
     Node *left;
     Node *right;
     Node(int x){
      val = x; Node* left = NULL; Node*right = NULL;
     }
  };
  
   
int maxDepth(Node* root) {
        
    // this is the base case when root is null we simply return 0
    if(root == NULL)return 0; 
    // here we are computing max height that is present in the left and 
    // right subtree, We are adding one for the current node. 
    else return max( maxDepth(root->left), maxDepth(root->right) + 1 ); 
        
}
int main()
{
    // constructing the tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->right->right = new Node(5);
    root->left->right->right = new Node(6);
    root->left->right->right->right = new Node(7);
    int height = maxDepth(root); 
    cout<<"The height of a binary tree is: "<<height<<endl;
    return 0;
}

 

Output :

The height of a binary tree is: 5

 

Time Complexity - O(N), as we are traversing every node once, the time complexity to compute the height of a binary tree is of the order N, where N is the number of nodes present in the tree. 

 

Space Complexity -The space complexity is O(H), where H is the height of the binary tree considering the stack space used during recursion while checking for symmetric subtrees. In the worst case(skewed binary tree), H can be equal to N, where N is the number of nodes in the tree.

 

This problem given above can be modified as - Given the node’s address, we have to find the height of that particular node in the tree. We can simply find the given node and start traversing to the left and right. The function to compute the following is :

 

Modified Height of a binary tree

 

#include<iostream>
 using namespace std; 
 
 struct Node {
     int val;
     Node *left;
     Node *right;
     Node(int x){
      val = x; Node* left = NULL; Node*right = NULL;
     }
  };
// this function is similar to maxDepth function above
int Solve(Node*root){
      if(root == NULL)return 0; 
      else return 1 + max( Solve(root->left), Solve(root->right) ); 
}
  // function to find the address where data is present 
void find(Node *root, int data){
    
    if(root == NULL)return; 
    if(root->val == data){
        cout<<"The height of a binary tree is: "<<Solve(root)<<endl;
        } 
    find(root->left, data); 
    find(root->right, data); 
}   


int main()
{
   // constructing the tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->right->right = new Node(5);
    root->left->right->right = new Node(6);
    root->left->right->right->right = new Node(7);
    find(root, 4); 
    return 0;
}

 

Output :

The height of a binary tree is: 3

 

Time Complexity - O(N), as we are traversing every node once, the time complexity to compute the height of a binary tree is N, where N is the number of nodes present in the tree. 

 

Space Complexity - The space complexity is O(H), where H is the height of the binary tree considering the stack space used during recursion while checking for symmetric subtrees. In the worst case(skewed binary tree), H can be equal to N, where N is the number of nodes in the tree.

Check out this problem - Mirror A Binary Tree

Depth of a node in a binary tree

Now let us calculate the depth of a node in a binary tree - 
We can simply calculate the depth of the tree by subtracting the height of the given node by the height of the root node. i.e -

 

Height(root) - Height(given node) 

binary tree

 

We can also calculate the depth of the binary tree by applying the recursive algorithm. We initiate the depth to be 0 initially when we are present at the root node. On every recursive call we add one to the depth and return when the given element for which depth has to be calculated is equal to the current element. 
 

#include<iostream>
 using namespace std; 
 
 struct Node {
     int data;
     Node *left;
     Node *right;
     Node(int x){
      data = x; Node* left = NULL; Node*right = NULL;
     }
  };
  
   
int maxDepth(Node * root, int val, int depth)
{
  // Root being null means tree doesn't exist.
  if (root == NULL)
    return 0;
  if(root->data == val)return depth; 
  
  // Get the depth of the left and right subtree 
  // using recursion.
  int leftDepth = maxDepth(root->left, val, depth + 1);
  int rightDepth = maxDepth(root->right, val, depth + 1);


 // if any of the subtree does not contain the element then it will return
 // null and we will simply return the value from the other tree. 
 return max(leftDepth, rightDepth); 
 
}


int main()
{
   // constructing the tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->right->right = new Node(5);
    root->left->right->right = new Node(6);
    root->left->right->right->right = new Node(7);
    int val = 4; 
    int depth = maxDepth(root, val, 1); 
    cout<<"The depth of a binary tree node " <<val << " is: "<<depth<<endl;
    return 0;
}

 

Output :

The depth of a binary tree is: 3

 

Time Complexity - O(N), as we are traversing every node once, the time complexity to compute the height of a binary tree is N, where N is the number of nodes present in the tree. In the worst case, our node will be a leaf node and we will end up traversing all the nodes. 

 

Space Complexity - The space complexity is O(H), where H is the height of the binary tree considering the stack space used during recursion while checking for symmetric subtrees. In the worst case(skewed binary tree), H can be equal to N, where N is the number of nodes in the tree.

 

Frequently Asked Questions

What is a binary search tree? 

A binary Search Tree or BST is a tree used to sort, retrieve, and search data. It is also a non-linear data structure in which the nodes are arranged in a particular order.

  • The left subtree of a node has nodes that are only lesser than that node’s key.
  • The right subtree of a node has nodes that are only greater than that node’s key.
  • Each node has distinct keys, and duplicates are not allowed in the Binary Search Tree.
  • The left and right subtree must also be a binary search tree.

Is DFS & preorder traversal the same? 

Preorder traversal is another variant of DFS. Depth-first-search (DFS) traverses the search tree as much as possible before proceeding to the next sibling, which is similar to pre-order traversal.

 

Conclusion

In this article, we discussed the solution to achieve the height/depth of a binary tree. This is an easy recursive problem on binary trees and can be solved using a simple application of recursion. This concept is a very important topic and has applications in other questions for the binary tree data structure. You can also refer to our course on master tree data structure to understand Trees.

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Binary Tree using dstructure library in Python
Next article
What is the difference between Full and Complete Binary Tree?
Live masterclass