Height and Depth of Binary Tree

Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

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

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 right )
return max( leftD, rightD)+1
C++ Program to Find Depth of Binary Tree
#include
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

X ITM Cloud News

Emily

Next Post

Python Tic Tac Toe Game

Sun Nov 24 , 2019
Spread the love          In this tutorial we are going to see how we can implement the tic tac toe game in Python. We can either make use of random numbers for the computer move or we can develop a simple algorithm which will play the role of a computer.  Let us […]
X- ITM

Cloud Computing – Consultancy – Development – Hosting – APIs – Legacy Systems

X-ITM Technology helps our customers across the entire enterprise technology stack with differentiated industry solutions. We modernize IT, optimize data architectures, and make everything secure, scalable and orchestrated across public, private and hybrid clouds.

This image has an empty alt attribute; its file name is x-itmdc.jpg

The enterprise technology stack includes ITO; Cloud and Security Services; Applications and Industry IP; Data, Analytics and Engineering Services; and Advisory.

Watch an animation of  X-ITM‘s Enterprise Technology Stack

We combine years of experience running mission-critical systems with the latest digital innovations to deliver better business outcomes and new levels of performance, competitiveness and experiences for our customers and their stakeholders.

X-ITM invests in three key drivers of growth: People, Customers and Operational Execution.

The company’s global scale, talent and innovation platforms serve 6,000 private and public-sector clients in 70 countries.

X-ITM’s extensive partner network helps drive collaboration and leverage technology independence. The company has established more than 200 industry-leading global Partner Network relationships, including 15 strategic partners: Amazon Web Services, AT&T, Dell Technologies, Google Cloud, HCL, HP, HPE, IBM, Micro Focus, Microsoft, Oracle, PwC, SAP, ServiceNow and VMware

.

X ITM