CareerCup

#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
Node *left, *right;
};

Node* newNode(int data) {
Node *temp = new Node();
temp->data = data;
temp->left = NULL;
temp->right = NULL;

return temp;
}

int minTimeUtil(unordered_map<Node*, int> &minTime ,Node *root) {
if(root) {
minTimeUtil(minTime, root->left);
minTimeUtil(minTime, root->right);

if(root->left == NULL && root->right == NULL)
minTime[root] = 1;
else {
minTime[root] = min(root->left!=NULL?minTime[root->left]:INT_MAX, root->right!=NULL?minTime[root->right]:INT_MAX) + 1;
}
}
}

int main()
{
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(8);
root->left->left->left = newNode(6);
root->left->left->right = newNode(7);

unordered_map<Node*, int> minTime;
minTimeUtil(minTime, root);

int ans = 0;
for(auto n:minTime) {
cout<<n.first<<" "<<n.second<<endl;
ans = max(ans, n.second);
}
cout<<ans<<endl;

return 0;
}

/*
The tree will burn in k ms, where k is the diameter of the tree.
The below is not a formal proof ( and may be wrong!)

Find the diameter (k) of the tree and let the sequence of nodes
{N0, N1, N2,..Nj, Nj+1, ..,Nk} lie on the diameter (path).
Let us consider the following possibilities how the fire could be
started

Case (1):
The fire could be lit at node N0 or Nk and would take the
maximum hops to reach the other end of the diameter.
Also, think of the intermediate burnt state of the tree
where the fire has reached node Nj. Now the remaining part
of the diameter left intact is k-j. Can there exist any reachable
node at a distance greater than k-j from Nj ? The answer is no.
Because, this would be contradict the definition of diameter.
If such a node existed, then it would be included on/in the diameter
path. We can safely conclude that all nodes reachable from Nj will
burn before the fire reaches the other end of the diameter, Nk.
It is clear in this case that the fire would consume the tree in
just k ms

Case (2):
The fire is started at a leaf node, Nx, not in {N0, N1, N2,..Nj, Nj+1, ..,Nk}
In this case, the fire has to eventually reach a node on the diameter path.
Let the fire with source at Nx reach Nj on the diameter path. Let the difference
between path length (N0..Nj) and path length (Nx...Nj) be D'.
After reaching Nj, the fire will continue towards Nk will will take
path length ( Nj.. Nk) ms. So the tree will be consumed in (k MINUS D') ms

*/

Maximum would be 1ms * 2 * hight_of_the_Tree

In a perfectly balanced tree, we can start from the most far right leaf, it burns up to the root, then goes down to the far most left leaf.

Assuming we are given parent pointer in the tree:
Apply DFS from the leaf node (including the parent), add 1 ms for all nodes in your path until you reach end and recurse back to node where you started. Node keeps max cost after recursive return to itself, and returns that to its calling node. Once reached back to the leaf node, returned cost is the answer.

I think it will be equal to the distance from the starting leafnode(from the start point of fire) to the farthest leafnode in the tree. You can easily find that by doing a BFS from the leafNode and the lastNode visited during the BFS will be the farthest leafnode.

It will be equal to the l + s where l and s are the longest and shortest paths from the root to leaf node respectively. No need for bfs. As there is only one path in the tree to reach from one node to another. The proof is obvious.

The time required : - maximum distance of a node from the starting node.

If we are giving particular node(leaf) from which it is starting to burn.............Then total time required to burn whole tree will be equal to
" Max distance of another leaf from that node "
In worst case, it will be equal to 2* Height(Binary tree)

the ans is: 1ms * height of binary tree