Untitled

#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() {
	// your code goes here
	
	City c;
	c.getName();
	
	return 0;
}