Calculating the Diameter of a Binary Tree with C++

Question:

Calculating the Diameter of a Binary Tree with C++

Summary:

The diameter or the width of a binary tree is the number of nodes on the longest path between two end nodes.

The following diagram depicts two trees, each of which has a diameter of nine. The leaves that form the ends of the longest path are the ones that are shaded. It is important to note that each tree contains more than one path of length nine, but there is no path that is longer than nine nodes.

Solution:

/* Tree node structure used in the program

struct Node

{

int data;

struct Node* left;

struct Node* right;

Node(int x){

data = x;

left = right = NULL;

}

}; */

class Solution {

private:

int find(Node* root,int &maxi){

if(root==NULL){

return 0;

}

int left=find(root->left,maxi);

int right=find(root->right,maxi);

maxi=max(maxi,left+right);

return 1+max(left,right);

}

public:

// Function to return the diameter of a Binary Tree.

int diameter(Node* root) {

int maxi=0;

find(root,maxi);

return maxi+1;

}

};

Explanation:

This code defines a class Solution with a private member function find and a public member function diameter.

Node Structure: Defines a structure for tree nodes with data, left, and right pointers. It includes a constructor to initialize data and pointers.

Private Function find: Recursively calculates the height of the left and right subtrees of a given node while updating the maximum diameter (maxi) encountered so far. It returns the height of the subtree rooted at the current node.

Public Function diameter: Calls the find function to compute the maximum diameter of the binary tree. It initializes a variable maxi to store the maximum diameter encountered during traversal. Finally, it returns the maximum diameter by adding 1 to the computed maxi.

Answered by: >mahakalujjzvf0

Credit: >GeekforGeeks

>Python Error Solved: pg_config executable not found

>Set up Node.js & connect to a MongoDB Database Using Node.js

>Setting up a Cloud Composer environment: Step-by-step guide

>What is microservice architecture, and why is it better than monolithic architecture?

>What is pipe in Angular?

>What makes Python 'flow' with HTML nicely as compared to PHP?

>What to do when MQTT terminates an infinite loop while subscribing to a topic in Python?

>Creating custom required rule - Laravel validation

>How to configure transfers for different accounts in stripe with laravel?