Q:

Replace a tree node in a matched location of a binary tree

How to replace a matched node in a binary tree with prolog? Properties of tree: it is not a binary search tree, but every element is unique, so replace operation will effect one element in tree at maximum.
initial tree definition: 
tree('Q',
     tree('P',
          tree('R',
               empty,
               empty),
          tree('S',
               empty,
               empty)), 
     tree('T',
          empty,
          empty))

Let's say new node to replace node 'R' with tree('new', tree('child1', empty, empty), tree('child2', empty, empty))
expected result:
tree('Q',
     tree('P',
          tree(tree('new',
               tree('child1',
                    empty,
                    empty), 
               tree('child2',
                    empty,
                    empty)),
          tree('S',
                empty,
                empty)
               )),
     tree('T',
          empty,
          empty))

Current status of the code:
:- dynamic([tree/1]).

run:-
 retractall(tree(_)),
 assertz(tree(tree('Q', tree('P', tree('R', empty, empty), tree('S', empty, empty)), tree('T', empty, empty)))),
 retract(tree(T)),
 insert('newElement', T, NewTree),
 assertz(tree(NewTree)),
 tree(T),write(T),!.

insert(NewItem,empty,tree(NewItem,empty,empty)):- !.

insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):-
   true, %match function needs to be here
   !,insert(NewItem,Left,NewLeft).

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):-
    insert(NewItem,Right,NewRight).

A:

I've changed a bit the syntax of your tree, since it was too much verbose for my taste.
Maybe you could consider using a supported tree format, like XML (coded as element/3),
that would give you much power in pattern matching, via library(xpath). Anyway
replace_tree(Old, New, Old, New).

replace_tree(Old, New, t(Key, L, R), t(Key, L1, R1)) :-
    replace_tree(Old, New, L, L1),
    replace_tree(Old, New, R, R1).

% base case of the recursive data structure
replace_tree(_Old, _New, t, t).

yields
?- T=t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3,t,t))),t), replace_tree(t(3,X,Y),t(new,X,Y),T,O).
T = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t),
X = t(4, t, t),
Y = t(5, t, t),
O = t(1, t(2, t(new, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t) ;
T = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t),
X = Y, Y = t,
O = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(new, t, t))), t) ;
T = O, O = t(1, t(2, t(3, t(4, t, t), t(5, t, t)), t(6, t, t(3, t, t))), t) ;
false.

