Lecture 292:- Height and Count of Binary Tree

To calculate the height and count (number of nodes) of a binary tree, we can perform a simple depth-first traversal (postorder) of the tree. During the traversal, we can increment the count for each node visited and keep track of the maximum height encountered. Here's the C++ implementation to find the height and count of a binary tree:

cppCopy code

#include <iostream> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; int height(TreeNode* root) {    if (root == nullptr)        return 0;    int leftHeight = height(root->left);    int rightHeight = height(root->right);    return max(leftHeight, rightHeight) + 1; } int countNodes(TreeNode* root) {    if (root == nullptr)        return 0;    return countNodes(root->left) + countNodes(root->right) + 1; } int main() {    // Create a binary tree:    //        1    //       / \    //      2   3    //     / \    //    4   5    TreeNode* root = new TreeNode(1);    root->left = new TreeNode(2);    root->right = new TreeNode(3);    root->left->left = new TreeNode(4);    root->left->right = new TreeNode(5);    int treeHeight = height(root);    int nodeCount = countNodes(root);    cout << "Height of the Binary Tree: " << treeHeight << endl;    cout << "Number of nodes in the Binary Tree: " << nodeCount << endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left->left;    delete root->left->right;    delete root->left;    delete root->right;    delete root;    return 0; }

Output:

sqlCopy code

Height of the Binary Tree: 3 Number of nodes in the Binary Tree: 5

In this example, we calculate the height of the binary tree as 3 (the longest path from the root to any leaf node) and the number of nodes as 5.