Why do we need to find the node in the list?
The problem states that given a pair, you want to
find the relationship. Given each node, the relationship
is already stored on the node and searching the tree
wouldn't help any... Right?
If you have to find the nodes in the tree, then yes, I aggree, it is O(MN). But the way I read the problem is that there are M pairs of nodes. You must loop through each pair, (taking M time), then find the relation, (taking constant time since you have the nodes, and the values are stored on the nodes). Total
time = O(M+N).
Thanks... |