The technology describes scanning tree data structures (trees) for multiple processes, at least partly in parallel. A service scans a tree from a beginning tree element to an ending tree element on behalf of a process; while scanning, another process can join in the scan at an intermediate tree element location (e.g., a key). For the subsequent process, the service scans the tree based on the intermediate location to the tree end, thereby visiting tree elements in parallel until the tree end, then continuing from the tree beginning element to the intermediate location for the subsequent process. The service basically completes a full carousel-type revolution for each process. One or more other processes can join an ongoing scan at any time, facilitating further parallel tree element visits, while still obtaining a full scan of the entire set of tree elements. The service handles changing tree versions during the scanning.