Nearest node in a tree

Revision en1, by Breaking_Benjamin, 2015-10-04 23:31:57

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.

The problem is here as follows :

Given an unweighted tree of 'n' nodes ( n>=1 and n can go to 105 ) , Its nodes can be special or non special. Node 1 is always special and rest non special initially. Now ,There are two operations :

1.we can update any non special node to special node by an update operation by "U Node_Number"

OR

2.At any time , we can ask user "Q Node_Number" which should return that special node in tree closest to "Node_Number".

These operations can also go upto 105.

My Solution :

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.

But complexity is quadratic. Is this the most optimal way of going about this problem ?

Tags tree, bfs, dfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Breaking_Benjamin 2015-10-04 23:31:57 1073 Initial revision (published)