class Solution {
Node *targetPtr = NULL;
public:
int minTime(Node* root, int target)
{
unordered_map<Node*, Node*> parentMap;
parentMap.insert({root, NULL});
buildParentMap(root, parentMap, target);
queue<Node*> q;
set<Node*> st;
int timer = -1;
q.push(targetPtr);
st.insert(targetPtr);
while(!q.empty()) {
int qLen = q.size();
timer++;
for (int i = 1; i <= qLen; i++) {
Node* curr = q.front();
q.pop();
Node *parent = parentMap[curr];
Node *left = curr -> left;
Node *right = curr -> right;
if (parent != NULL && st.find(parent) == st.end()) {
st.insert(parent);
q.push(parent);
}
if (left != NULL && st.find(left) == st.end()) {
st.insert(left);
q.push(left);
}
if (right != NULL && st.find(right) == st.end()) {
st.insert(right);
q.push(right);
}
}
}
return timer;
}
void buildParentMap(Node* root, unordered_map<Node*, Node*> &parentMap, int target) {
if (root == NULL)
return;
if (root -> data == target)
targetPtr = root;
if (root -> left != NULL)
parentMap.insert({root -> left, root});
if (root -> right != NULL)
parentMap.insert({root -> right, root});
buildParentMap(root -> left, parentMap, target);
buildParentMap(root -> right, parentMap, target);
}
};