#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED

#include "list.h"

typedef struct utree_node {
    unsigned content;
    struct utree_node *sag, *sad;
} utree_node;

typedef utree_node *utree;

void init_indent();
void simple_print_utree_graph(utree t, const char *name);
void parenthesis_print_utree_graph(utree t, const char *name);

/** Produit l'arbre de Syracuse (tête valant 1) jusqu'à la profondeur n **/
/** voir interlude Syracusien, p144, dans Exercices & Problèmes d'Algorithmique **/
void syracuse_tree_growth(utree *pt, unsigned n);

/** 1.	Vérifier qu’un arbre (représenté par l’adresse de sa racine) est vide. **/
int is_empty_utree(utree t);

/** 2.	Créer et initialiser un nœud d’arbre (c’est à dire un arbre singleton). **/
utree new_singleton_utree(unsigned content);

/** 3.  Parcourir un arbre et afficher les éléments qu’il contient
    A   Suivant un parcours itératif de gauche à droite, en largeur. **/
void width_walker_utree_printer(utree t);

/** 3.  Parcourir un arbre et afficher les éléments qu’il contient
    B   Suivant un parcours itératif de gauche à droite, en profondeur. **/
void depth_walker_utree_printer(utree t);

/** 3.  Parcourir un arbre et afficher les éléments qu’il contient
    C   Suivant un parcours infixe de gauche à droite. **/
void infix_walker_utree_printer(utree t);

/** 4.	Libérer la mémoire occupée par un arbre (retourne le nombre de noeuds libérés). **/
unsigned delete_tree(utree t);

/** 5.	Retourner le nombre d’éléments d’un arbre. **/
unsigned nr_elements(utree t);

/** 6.	Retourner la hauteur d’un arbre. **/
unsigned get_depth(utree t);

/** 7.	Vérifier qu’un arbre b est le sous-arbre d’un arbre a **/
int is_sub_tree(utree a, utree b);

/** 8.	Retourner une liste simplement chaînée qui représente la branche [a, b]
        d’un arbre a si celle-ci existe, et une liste vide sinon. **/
list get_branch(utree a, utree b);

/** 9.	Créer un arbre parfait de profondeur n dont les valeurs des nœuds sont exactement
        les index des nœuds suivant un parcours en largeur (index 1 pour la racine). **/
utree new_perfect_tree(unsigned n, unsigned e);

/** 10.	Vérifier qu’un arbre binaire est un arbre binaire de recherche. **/
utree min(utree t);
utree max(utree t);
/// la version naïve
int is_bst(utree t);
/// une version moins naïve
int is_bst_v2(utree t, unsigned *min, unsigned *max);


#endif // TREE_H_INCLUDED