Height and Depth of Binary Tree

In this tutorial, we will learn how to find height and depth of binary tree with program implementation in C++. It is one of the most commonly used non-linear data structures. We will learn about:

• What is the height of a binary tree?
• Algorithm and implementation for finding height of Binary tree
• What is the depth of a binary tree?
• Algorithm and implementation for finding depth of Binary tree

Many times, people are confused between Depth and Height of Binary tree. It is because the depth of binary tree is always equal to the height of binary tree but they are not the same and using the terms interchangeably is not correct. So, it is important for us to understand the difference between the Height and Depth of Binary tree.

Height of Binary Tree

“Dream as high as the sky and as Deep as the ocean.”

As the quote on top says sky is what we should see while calculating height. The height of binary tree is the measure of length of the tree in the vertical direction. It is measured in upward direction that is from child to parent. The leaf nodes have height of 0 as there is no nodes below them. The height of the root node of the binary tree is the height of the whole tree. The height of a particular node is the number of edges on the longest path from that node to a leaf node.

Finding the Height of Binary Tree

To find the height of the binary tree we will recursively calculate the height of the left and right subtree of a node. To find the heights of left and right subtrees we use in-order traversal. After finding the height of both left and right subtree we will store the height of the subtree which has maximum value and add 1 to it to include the current level of tree.

Algorithm

FindHeight( Node root)
        If root == NULL 
                return 0
        else
                int leftH = FindHeight ( root->left )
                int rightH = FindHeight(root->right ) 
        return max( leftH, rightH )+1

C++ Program to Find Height of Binary Tree

#include <bits/stdc++.h> 

using namespace std; 

/* structure of a binary tree */
struct node 
{  
        int data;    // to store the value of a node in tree
        node* left;   // pointer to the left child 
        node* right;   // pointer to the right child
}; 

/* function to find the maximum height of binary tree */
int FindHeight(node* node) 
{ 
        if (node == NULL)  // when the subtree is empty
                return 0; 
                
        else
        { 
                int leftH,rightH;
                
                /*find the height of left subtree */
                leftH = FindHeight(node->left); 
                
                /*find the height of right subtree */
                rightH = FindHeight(node->right); 
        
                /* return the maximum height */
                if (leftH > rightH) 
                return(leftH + 1); 
                
                else 
                return(rightH + 1); 
        } 
} 

/* function to get new node for the tree */
node* getNode(int data) 
{ 
        node* newNode = new node(); 
        newNode->data = data; 
        newNode->left = NULL; 
        newNode->right = NULL; 
        
        return(newNode); 
} 
        
int main() 
{ 
        /* creating the binary tree */
        node *root = getNode(1); 
        root->left = getNode(2); 
        root->right = getNode(3); 
        root->left->left = getNode(4); 
        root->left->right = getNode(5); 
        root->right->left = getNode(6); 
        root->right->right = getNode(7); 
        
        cout << "The Height of the binary tree is " << FindHeight(root); 
        return 0; 
}

Output:

The Height of the binary tree is 3

Depth of Binary Tree

Think of ocean and the quote above while calculating depth. The depth is a measure of how far a node is from the root of the tree. The depth of the ocean is calculated with respect to the sea level similarly the depth of any node in binary tree is measured with respect to the root node of the tree. The depth of a particular node in binary tree is the number of edges from the root node to that node. The depth of binary tree is the depth of the deepest node (leaf node).

To find the depth of the binary tree we will recursively calculate the depth of the left and right child of a node. After finding the depth of both left and right child we will store the depth of the child which has maximum value and add 1 to it to include the current level of tree.

Algorithm

FindDepth( Node root)
        If root == NULL 
                return 0
        else
                int leftD = FindDepth ( root->left )
                int rightD = FindDepth (root->right ) 
        return max( leftD, rightD)+1

C++ Program to Find Depth of Binary Tree

#include <bits/stdc++.h> 
using namespace std; 

/* structure of a binary tree */
struct node 
{  
        int data;    // to store the value of a node in tree
        node* left;   // pointer to the left child 
        node* right;   // pointer to the right child
}; 

/* Finding the depth of tree */
int FindDepth(node* node) 
{ 
        if (node == NULL)  // when the subtree is empty
                return 0; 
                
        else
        { 
                int leftD,rightD;
                
                /*find the depth of left child */
                leftD = FindDepth(node->left); 
                
                /*find the depth of right child */
                rightD = FindDepth(node->right); 
        
                /* return the maximum depth */
                if (leftD > rightD) 
                return(leftD + 1); 
                
                else 
                return(rightD + 1); 
        } 
} 

/* function to get new node for the tree */
node* getNode(int data) 
{ 
        node* newNode = new node(); 
        newNode->data = data; 
        newNode->left = NULL; 
        newNode->right = NULL; 
        
        return(newNode); 
} 
        
int main() 
{ 
        /* creating the binary tree */
        node *root = getNode(1); 
        root->left = getNode(2); 
        root->right = getNode(3); 
        root->left->left = getNode(4); 
        root->left->right = getNode(5); 
        root->right->left = getNode(6); 
        root->right->right = getNode(7); 
        root->left->right->right = getNode(10); 
        
        cout << "The Depth of the binary tree is " << FindDepth(root)-1; 
        return 0; 
}

Output:

The Depth of the binary tree is 3

Comment down below if you have queries related to height and depth of binary tree.

The post Height and Depth of Binary Tree appeared first on The Crazy Programmer.