# Untitled

unknown
plain_text
2 years ago
1.7 kB
10
Indexable
Never
```#include <iostream>
using namespace std;

// City -- Node

// Binary Tree - Node class
class Node {

public:
int data;
Node * leftPtr;
Node * rightPtr;

Node(int d){
data = d;
leftPtr = NULL;
rightPtr = NULL;
}

};

int height(Node * root){

if(!root) return 0;

return 1 + max(height(root->leftPtr), height(root->rightPtr));

}

// approach - three things - 1. diameter of left sub tree, 2. diameter of right subtree
// 3. left subtree height + right subtree height

int diameter(Node * root){

if(!root) return 0;

int d1 = diameter(root->leftPtr);
int d2 = diameter(root->rightPtr);
int d3 = height(root->leftPtr) + height(root->rightPtr);

return max(d1, max(d2, d3));

}

class Pair {
public:
int height;
int diameter;
}

Pair diameter2(Node * root){

Pair current;

if(!root){
current.diameter = 0;
current.height = 1;
return current;
}

Pair left = diameter2(root->left);

Pair right = diameter2(root->right);

current.diameter = max(left.height + right.height, max(left.diameter, right.diamter));
current.height = max(left.height, right.height) +1;

return current;

}

// get the root from this function
Node * buildTree(){

int data;
cin >> data;

if(data == -1){
return NULL;
}

// create a new node
Node * root = new Node(data);
root -> leftPtr = buildTree();
root-> rightPtr = buildTree();

return root;
}

// to pass the root in this function
// void buildTree(Node * &root){

// 	int data;
// 	cin >> data;

// 	if(data == -1){
// 		return;
// 	}

// 	root = new Node(data);
// 	buildTree(root->leftPtr);
// 	buildTree(root->rightPtr);
// }

int main() {