Following is the test i created for my implementation of the above problem.
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <sys/time.h>
using namespace std;
class Node{
public:
Node * left;
Node * right;
int val;
Node(int v){
left = NULL;
right = NULL;
val = v;
}
};
void traverseAndAdd(Node * n, vector<Node *> * nodes){
if(n == NULL) return;
nodes->push_back(n);
traverseAndAdd(n->left, nodes);
traverseAndAdd(n->right, nodes);
}
//someone else's implementation..assumed correct
int diameterOpt(Node * n, int * height){
int lh, rh = 0;
if(n == NULL){
*height = 0;
return 0;
}
int left_diameter = diameterOpt(n->left, &lh);
int right_diameter = diameterOpt(n->right, &rh);
*height = max(lh, rh) + 1;
return max(lh + rh + 1, max(left_diameter, right_diameter));
}
int heightOf(Node * n){
if(n == NULL) return 0;
return 1 + max(heightOf(n->left), heightOf(n->right));
}
int max_length = -1;
//my implementation
void maxPathLength(Node * n){
if(n == NULL) return;
int left_height = heightOf(n->left);
int right_height = heightOf(n->right);
if((left_height + right_height + 1) > max_length)
max_length = left_height + right_height + 1;
if(left_height >= right_height){
maxPathLength(n->left);
}
else
{
maxPathLength(n->right);
}
}
double getTime()
{
struct timeval tp;
gettimeofday(&tp, NULL);
return ((double) tp.tv_sec + (double) tp.tv_usec * 1e-6);
}
int main()
{
double starttime = getTime();
for(int k=0;k<20000;k++){
vector<int> nos;
int length = k+1;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////CREATE A BINARY TREE WITH k NODES///////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
for(int i=1;i<=length;i++)
nos.push_back(i);
int len = nos.size();
vector<Node *> nodes;
for(int i=0;i<len;i++){
nodes.push_back(new Node(nos[i]));
}
for(int i=1;i<=(len/2);i++){
nodes[i-1]->left = nodes[2*i - 1];
nodes[i-1]->right = nodes[2*i];
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////KEEP CUTTING RANDOM BRANCH TILL THE TREE HAS JUST THE ROOT NODE/////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
while(nodes.size() != 1){
int index_to_delete = rand() % nodes.size();
int ri = rand()%2;
//////HERE WE CUT EITHER LEFT OR RIGHT BRANCH RANDOMLY
if(ri == 0){
nodes[index_to_delete]->left = NULL;
}
else
{
nodes[index_to_delete]->right = NULL;
}
Node * temp = nodes[0];
int height = 0;
maxPathLength(temp); //MY IMPLEMENTATION
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////NOW COMPARING THE OUTPUT OF MY IMPLEMENTATION WITH THE OUTPUT OF THE CORRECT SOLUTION////////////////////////////
////////////////////////////////////////(diameterOpt is correct implementation)//////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//CHECKING MY IMPLEMENTATION WITH
if( max_length != diameterOpt(temp, &height)){
cout << "Failed ..." << endl;
}
max_length = -1;
nodes.clear();
//THIS UPDATES THE TREE WITH CUT BRANCH TAKEN OUT
traverseAndAdd(nodes[0], &nodes);
}
}
cout << endl;
cout << "Total time taken was " << getTime() - starttime << endl;
cout << "Done" << endl;
return 0;
}
The output of the program was
It was a relief to see no "Failed ...". Though not a guarantee it gives more credence to the implementation.
No comments:
Post a Comment