The Finite Volume Particle Method (FVPM) is a meshfree particle generalization of the established Finite Volume Method. Combining the advantages of the Finite Volume Method with those of classical particle schemes makes it an interesting and promising approach: It is quantity conserving, stable, and due to its Arbitrary-Lagrangian-Eulerian-property (ALE-property) perfectly suited for free-surface simulations or strongly changing domains. Although FVPM is very promising, it includes many computationally expensive subroutines such as particle movement, changing neighborhoods, and the computation of particle interaction. Furthermore, current implementations lack in parallelization. We present a tree-based FVPM version that overcomes these issues -- it lowers the computational costs and enables efficient parallelization for the first time to the best of our knowledge. To this end, we add an underlying tree structure, associate particles to tree cells and introduce a new particle velocity correction exploiting the ALE-property of FVPM. The tree not only simplifies neighbor search, it also enables the use of a space-filling curve parallelization with dynamic load balancing, which is crucial to get an efficient parallelization in a strongly changing particle discretization. Furthermore, this velocity correction avoids classical issues of particle methods such as particle crowding or holes near shock fronts. We present numerical benchmark test cases, which show stability and performant scaling behavior of our implementation. Altogether, we adapt the classical implementation of FVPM in various aspects to enable not only a conservative simulation but make it applicable to large, high-dimensional problems and engineering applications.