This is not a bug. However, this is a great opportunity to shed some light on the inner workings of Replace. What happens, in short, is that it first fully processes the expression, without calling main evaluator on any of its replaced parts, and only then the entire transformed expression is given to the evaluator.
Basically, we can visualize what happens using this:
held = Replace[Hold[Evaluate[x]],t_tree :> (Print[t, t]; 0), {0, Infinity}]
(*
Hold[
Print[tree["A", {Print[tree["B", {1, 2}], tree["B", {1, 2}]]; 0, 3}],
tree["A", {Print[tree["B", {1, 2}], tree["B", {1, 2}]]; 0, 3}]]; 0
]
*)
which shows the origin of extra Print.
What you were assuming was that the evaluation of replaced parts happens right after they were replaced, which would mean that Replace would have to call main evaluator after replacement at each level. Instead, the action of Replace is semantically equivalent to
ReleaseHold[Replace[Hold[expr], rules, spec] spec]]
which may produce different result if side effects are injected by replacement rules.
