====== Insert into tree ======
{{tag>trees}}
===== Description =====
Inserting element to a binary tree as a leaf

**Source**:  PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
===== Download =====
Program source code: {{insert_into_tree.pl}}
===== Listing =====
<code prolog>
% Figure 9.10  Inserting an item as a leaf into the binary dictionary.

% addleaf( Tree, X, NewTree):
%   inserting X as a leaf into binary dictionary Tree gives NewTree

addleaf( nil, X, t( nil, X, nil)).

addleaf( t( Left, X, Right), X, t( Left, X, Right)).

addleaf( t( Left, Root, Right), X, t( Left1, Root, Right))  :-
  gt( Root, X),
  addleaf( Left, X, Left1).

addleaf( t( Left, Root, Right), X, t( Left, Root, Right1))  :-
  gt( X, Root),
  addleaf( Right, X, Right1).

gt(X,Root):-X>Root.
</code>
===== Comments =====