Consider the following minimal examples. This one works as expected, replacing trees starting from the inside with a numerical value.

ClearAll[tree];
x = tree["A", {tree["B", {1, 2}], 3}];
Replace[x, t_tree :> (Print[t]; 0), {0, Infinity}]

During evaluation of In[1]:= tree[B,{1,2}]  
During evaluation of In[1]:= tree[A,{0,3}]  
Out[1]= 0

This one however introduces an unexpected intermediate step.

Replace[x, t_tree :> (Print[t, t]; 0), {0, Infinity}]

During evaluation of In[3]:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In[3]:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In[3]:= tree[A,{0,3}]tree[A,{0,3}]
Out[3]= 0

While the results are the same, anything more complicated than Print[t] causes extra stages to appear. Hence I cannot reliably use Replace to collect replaced parts (instead of printing them), as there would be excess entries at the end, see next example:

y = {}; Replace[x, t_tree :> (AppendTo[y, t]; 0), {0, Infinity}]; y

{tree["B", {1, 2}], tree["A", {0, 3}]}

y = {}; Replace[x, t_tree :> (AppendTo[y, t -> Mean@Last@t]; 0), {0, Infinity}]; y

{tree["B", {1, 2}] -> 3/2, tree["B", {1, 2}] -> 3/2, tree["A", {0, 3}] -> 3/2}

There are three replacements instead of two.