<p>You are given the <code>root</code> of a binary tree with <strong>unique</strong> values, and an integer <code>start</code>. At minute <code>0</code>, an <strong>infection</strong> starts from the node with value <code>start</code>.</p>

<p>Each minute, a node becomes infected if:</p>

<ul>
	<li>The node is currently uninfected.</li>
	<li>The node is adjacent to an infected node.</li>
</ul>

<p>Return <em>the number of minutes needed for the entire tree to be infected.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png" style="width: 400px; height: 306px;" />
<pre>
<strong>Input:</strong> root = [1,5,3,null,4,10,6,9,2], start = 3
<strong>Output:</strong> 4
<strong>Explanation:</strong> The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/25/image-20220625231812-2.png" style="width: 75px; height: 66px;" />
<pre>
<strong>Input:</strong> root = [1], start = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> At minute 0, the only node in the tree is infected so we return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 10<sup>5</sup>]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
	<li>Each node has a <strong>unique</strong> value.</li>
	<li>A node with a value of <code>start</code> exists in the tree.</li>
</ul>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    //parent question (code copied from, later modified; comments are outdated/wrong)- https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
    //NOTE- Almost similar to parent question, we simply run DFS and return the distance of farthest away node from start (start is assumed to be target node)
    //Working- we intend to do DFS from root. For this we first calculate distance of target from root. Suppose a node is at distance 'x'
    //from target then it's child will be distance 'x+1' from target (if target is not in child subtree), but child will be at dist 'x-1'
    //if target is in subtree of child. To know whether the target is subtree of a given node or not. We calculate path from root to target
    //and add all the path nodes in a set (presence of node in set denotes target is n subtree of node) and moving downwards from node's parent
    //to that node will actually reduce the distance. If node is not in set, moving from parent to that node will increase the distance
    //Note: all the nodes in root to target path are actually the ancestor nodes of the target
    int dfsApproachByPreparingAncestorNodesSet(TreeNode* root, int targetNodeVal){
        //vector<int> answerNodes; //our answer (nodes at distance k from target; 
        unordered_set<int> ancestorNodes; //set to store all the nodes of "root to target" path (ancestor nodes of target)
        prepareAncestorNodesSetUsingDFS(root, targetNodeVal, ancestorNodes);
        int distanceBetweenRootAndTarget = ancestorNodes.size() - 1; //this is the distance between root node and target node
        //to start the DFS from root we need it's distance from target, so we can calculate it's child's distance from target 
        //why we are doing + 2? in dfs function we will realise that target is in subtree of root. That function assumes that parent node always increases the distance by 1
        //to correct the distance (in case target is in subtree of currNode) it will reduce the distance by 2. If confused see comments on dfsAndCalculateDistanceFromTarget
        return dfsAndCalculateDistanceFromTarget(root, distanceBetweenRootAndTarget + 2, ancestorNodes); //prepare answer nodes by doing dfs on tree from root
    }

    //traverse over tree in dfs style and prepare a vector containing all the nodes from root to target. return value- whether targetNode is present in subtree of currNode
    //or not (need this to determine whether to keep or remove currNode while backtracking)
    bool prepareAncestorNodesSetUsingDFS(TreeNode* currNode, int targetNodeVal, unordered_set<int>& ancestorNodes){
        if(currNode == NULL){
            return false;
        }
        ancestorNodes.insert(currNode->val); //we assume currNode is in path from root to target
        if(currNode->val == targetNodeVal){ //currNode is actually the target node
            return true; //return true so that previous recursion call (parent) knows that target is in that node's subtree
        }
        //call to left and right subtree
        bool isTargetPresentInLeftSubtree = prepareAncestorNodesSetUsingDFS(currNode->left, targetNodeVal, ancestorNodes);
        bool isTargetPresentInRightSubtree = prepareAncestorNodesSetUsingDFS(currNode->right, targetNodeVal, ancestorNodes);
        if(isTargetPresentInLeftSubtree || isTargetPresentInRightSubtree){ //if target is actuallu present in curent subtree
            return true; //return true and do not remove currNode from ancestorNodes
        }
        else{ //if target node is not found in currNode's subtree
            ancestorNodes.erase(currNode->val); //remove currNode from ancestors
            return false; //return false denoting target was not found in currNode's subtree
        }
    }

    //do a dfs from root. if dist of currNode from target = x, then distance of currnode's child from target = x+1 (while making dfs calls we assume that 
    //target is not in child's subtree). While processing child we check if target is in it's (child's) subtree, if it is we do currDistance-=2 (refer below)
    int dfsAndCalculateDistanceFromTarget(TreeNode* currNode, int currNodeDistFromTarget, unordered_set<int>& ancestorNodes){
        if(currNode == NULL){
            return INT_MIN;
        }
        if(ancestorNodes.find(currNode->val) != ancestorNodes.end()){ //the target node is actually in currNode's subtree, so instead of increasing the distance by 1
            //we should've reduced the distance by 1, so now we reduce it by 2
            currNodeDistFromTarget -= 2;
        }

        //cout<<currNode->val<<" "<<currNodeDistFromTarget<<endl;

        //(while making dfs calls) we assume that target is not in subtree of any child so we increase their distances by 1
        //however if target is actually present in their (child's) subtree, we will correct it later (when function runs for those childs)
        int maxDistFromLeftSubtree = dfsAndCalculateDistanceFromTarget(currNode->left, currNodeDistFromTarget + 1, ancestorNodes);
        int maxDistFromRightSubtree = dfsAndCalculateDistanceFromTarget(currNode->right, currNodeDistFromTarget + 1, ancestorNodes);
        //why we are considering currNodeDist also? in case currNode is a leaf node
        return max(currNodeDistFromTarget, max(maxDistFromLeftSubtree, maxDistFromRightSubtree));
    }

    //for all the nodes prepare a parent vector such that vec[i] gives the parent node of the node with value 'i'
    //we also save target node in a reference variable when we find it
    void dfsTraverseAndPrepareParents(TreeNode* currNode, vector<TreeNode*>& parentNodes, int targetNodeVal, TreeNode*& target){
        if(currNode->val == targetNodeVal){
            target = currNode;
        }
        if(currNode->left != NULL){
            parentNodes[currNode->left->val] = currNode; //the parent node for left child's (value) is currNode
            dfsTraverseAndPrepareParents(currNode->left, parentNodes, targetNodeVal, target);
        }
        if(currNode->right != NULL){
            parentNodes[currNode->right->val] = currNode; //the parent node for right child's (value) is currNode
            dfsTraverseAndPrepareParents(currNode->right, parentNodes, targetNodeVal, target);
        }
    }


    //parent question (code copied from, later modified; COMMENTS ARE COPIED/WRONG)- https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
    //NOTE- Almost similar to parent question, we simply run BFS from target/start node and return the distance of farthest away node from start/target
    //Intuition: We want to do a BFS from the target node so we can visit and store all nodes at 'k' distance from target.
    //In tree however by default we can't move in all the possible direction and can only move in downward direction.
    //To move in upward direction we need to store parents of all nodes in some DS like array/ map, using which we can move upwards also.
    //Effectively we are converting the tree to a undirected graph and then running BFS from target node upto k distance nodes 
    int storeParentAndDoBFS(TreeNode* root, int targetNodeVal){
        //parent of any node say x can be found as parentNodes[x->val];
        vector<TreeNode*> parentNodes((1e5)+2, NULL); //why (1e5)+1? because 1 <= Node.val <= 10^5
        TreeNode* target;
        dfsTraverseAndPrepareParents(root, parentNodes, targetNodeVal, target); //prepare parentNodes vector, also save target node
        vector<int> answerNodes; //our answer (nodes at distance k from target)
        //do a BFS from currNode
        queue<TreeNode*> nextNodesToVisit;
        nextNodesToVisit.push(target); //start BFS traversal from target/start node
        //just after/before the start of the for loop, all the nodes present in queue will be at same distance
        int distanceOfCurrentNodesInQueue = 0; //distance of current nodes in queue from target at the abovementioned point
        vector<int> visited((1e5)+2, false); //if we have visited a node say x, then visited[x->val] will be true, this is needed
        //so that we don't visit previous node from the next node again (in a circular manner)
        while(!nextNodesToVisit.empty()){
            int nodesAtCurrentDistance = nextNodesToVisit.size(); //at this point the queue will only contain all (and only) the nodes of tree 
            //whose distance from target = distanceOfCurrentNodesInQueue
            for(int index = 0; index < nodesAtCurrentDistance; ++index){ //process all the node with a specific distance from target in this loop 
                TreeNode* currNode = nextNodesToVisit.front();
                nextNodesToVisit.pop();
                visited[currNode->val] = true;
                //move towards tree parent (not the bfs parent), it will be at currNodeDistance + 1 distance from target 
                //and will be traversed in next for loop and not this one
                if(parentNodes[currNode->val] != NULL && (!visited[parentNodes[currNode->val]->val])){ //if currNode has a unvisited parent
                    nextNodesToVisit.push(parentNodes[currNode->val]); //add parent to BFS queue
                }
                //add left/right unvisited child in BFS queue as usual (they will be at currNodeDistance + 1 distance from target)
                if(currNode->left != NULL && (!visited[currNode->left->val])){
                    nextNodesToVisit.push(currNode->left);
                }
                if(currNode->right != NULL && (!visited[currNode->right->val])){
                    nextNodesToVisit.push(currNode->right);
                }
            }
            distanceOfCurrentNodesInQueue += 1; //at this point, all the nodes present in queue will be at this distance
        }
        return distanceOfCurrentNodesInQueue-1; //last increment was done when queue was empty (there wee no nodes at that distance)
    }

    //TODO- update comments, they are copied from parent question and are wrong
    //TODO- Other approaches, DFS approach is quite slow
    int amountOfTime(TreeNode* root, int start) {
        //return dfsApproachByPreparingAncestorNodesSet(root, start);

        return storeParentAndDoBFS(root, start);
    }
};
208700