Fast Quadtree Query

Question

Suppose I have a quadtree of heightmap with the root the coarsest representation, and the leaves the most refined. Near the camera I want to draw the most detail, so I traverse the tree based on node distance to the camera. At each node where I stop recursing, I want to draw that node (i.e., the heightfield) at that detail. I put these nodes in a list S.

Now that I know what nodes to draw at what detail, given an arbitrary point (x,y) in the world (ignoring height z), I want to know which node in S the point intersects quickly and on the GPU. So some ideas are:

1. Iterate through S and do a bounds/point intersection test. Seems slow.
2. Pack the quadtree with leaves in S in an array representation so I can traverse on the GPU. More complicated, still have to traverse tree, but faster than going through every node.
3. Create a uniform grid representing the most refined quadtree level where the grid basically gives me the cell depth and cell offset at each entry. This would be very fast grid lookup, but potentially a lot of memory.

My question is: Any other ideas I am missing?