title: Nearest node in a tree
body: <p>Recent I encountered this problem on trees whose solution I found in O(n*q) . I am thinking if there is much better way to deal this with lesser complexity.</p>
  
  <p>The problem is here as follows : </p>
  
  <p>Given an unweighted tree of 'n' nodes ( n>=1 and n can go to 10<sup>5</sup> ) , Its nodes can be special or non special. Node 1 is always special and rest non special initially. Now ,There are two operations :</p>
  
  <p>1.we can update any non special node to special node by an update operation by <strong><em>"U Node_Number"</em></strong> </p>
  
  <p>OR</p>
  
  <p>2.At any time , we can ask user <strong><em>"Q Node_Number"</em></strong> which should return that special node in tree closest to "Node_Number".</p>
  
  <p>These operations can also go upto 10<sup>5</sup>.</p>
  
  <p>My Solution : </p>
  
  <p>I thought of creating adjacency list. For operation 1, I can keep record of special or Non special by boolean flag. But for operation 2 , my solution comprises of doing BFS whenever "Q Node_Number" is asked taking "Node_Number" as root to begin my BFS. </p>
  
  <p>But complexity is quadratic. Is this the most optimal way of going about this problem ?</p>