function Tree = learnTree(X,y,k)
% Tree = learnTree(X,y,k)
%
% X,y labeled examples to train
% k minimal number of leaf examples
%
% Trains decision tree and returns tree structure

if nargin < 2
	error('Too few input parameters.');
end
if nargin < 3
	k = 1;
end
y_pos = length(find(y > 0));
y_neg = length(y) - y_pos;

Tree.nodes = 0; % kodiert Struktur des Baumes
Tree.attr  = 0; % gewähltes Spliiting-Attribut
Tree.class = (y_pos > y_neg); % Klasse des Knotens (nur für Blätter wichtig)
Tree.IG    = 0; % Wert des Information Gain (nur zur Visualisierung)

if y_pos == 0 || y_neg == 0
	% es gibt nur eine Klasse im Blatt
	return
end

IG_max = 0;
for i = 1:size(X,2)
	% compute IG für das i-te Attribut
	j_pos = find(X(:,i) >  0);  % Index der positiven Label in Bezug 
                                % auf Attribut i
	j_neg = find(X(:,i) <= 0);
	IG = infoGain(y(j_pos), y(j_neg));
    %stelle sicher, dass mindestens k beispiele im knoten sind
	if IG > IG_max && length(j_pos) >= k && length(j_neg) >= k                                                                 
		IG_max = IG;
		i_max  = i;
	end
end
if IG_max < 2e-5
	% (fast) kein Zugewinn oder zu wenige Beispiele im Blatt (Mehrheitsklasse vorhersagen)
	return
end

j_pos = find(X(:,i_max) >  0);
j_neg = find(X(:,i_max) <= 0);

% left subtree
Tree1 = learnTree(X(j_pos,:), y(j_pos), k);

% right subtree
Tree2 = learnTree(X(j_neg,:), y(j_neg), k);

% join subtrees
Tree.nodes = [0, 1, Tree1.nodes(2:end) + 1, 1, ...
              Tree2.nodes(2:end) + length(Tree1.nodes) + 1];
Tree.attr  = [i_max, Tree1.attr, Tree2.attr];
Tree.class = [Tree.class, Tree1.class, Tree2.class];
Tree.IG    = [IG_max, Tree1.IG, Tree2.IG];
