A system, computer readable medium, and method are disclosed for performing a tree traversal operation. The method includes the steps of executing, via a processor, a tree traversal operation for a tree data structure, receiving a transformation node that includes transformation data during the tree traversal operation, and transforming spatial data included in a query data structure based on the transformation data. Each node in the tree data structure is classified according to one of a plurality of nodesets, the plurality of nodesets corresponding to a plurality of local coordinate systems. The processor may be a parallel processing unit that includes one or more tree traversal units, which implement the tree traversal operation in hardware, software, or a combination of hardware and software.