Randomized Branch Sampling (RBS) is a multistage sampling procedure using natural branching in order to select samples for the estimation of tree characteristics. Usually, sampling units are selected with unequal probabilities. Conventional RBS uses sampling with replacement (SWR) for repeated sampling on the first stage, and the sample size equals 1 on all subsequent stages, thus resulting in n so-called sample paths. When the sampling fraction is large multiple selections of first stage units are likely. Sampling without replacement (SWOR) at the first stage is an alternative that is expected to increase efficiency of the procedure. In this case, the second stage sample size m must be larger than 1 to enable unbiased variance estimation. In the present study, a theoretical and an empirical comparison of the conventional RBS and the SWOR variant was accomplished. Requiring a certain precision of the RBS estimation, the conventional RBS method is mostly more time-consuming than the variant with SWOR at the first stage. Only if m = 1 is chosen as second stage sample size for the SWOR RBS, this is often more time-consuming. In those cases, conventional RBS is up to 5% cheaper. In general, the larger m is, the more expensive is conventional RBS compared with the variant with swor at the first stage. The smaller the ratio of the variance between the primary units to the total variance of the estimate, the larger is the advantage of the SWOR variant. Generally, it can be shown that the gain of efficiency by SWOR is larger in case of weak correlations between auxiliary and target variable.