#ifndef _TREE_H
#define _TREE_H

#include "list.h"

#define  RECURSIVE     0
#define  STACK_BASED   1
#define  ITERATIVE     2

#define  INORDER       0
#define  PREORDER      1
#define  POSTORDER     2

typedef struct tree Tree;
struct tree {
    Node *root;                     // pointer to root node of tree
    char  max_height;               // max height of tree (0 = unlimited)
    char  height;                   // current height of tree
    Tree *(*copy)(Tree *         ); // copy tree (function pointer)
    Tree *(*grab)(Tree *, Node **); // grab node (function pointer)
    List *(*walk)(Tree *, char   ); // walk tree (function pointer)
};

Tree *mktree    (char           );  // create new tree

Tree *set_mode  (Tree *, char   );  // set tree mode (recurse, stack, iter)

Tree *addnode   (Tree *, Node * );  // add given node to tree

Tree *copytree_s(Tree *         );  // copy/duplicate given tree (stack-based)
Tree *copytree_r(Tree *         );  // copy/duplicate given tree (recursion)
Tree *copytree_i(Tree *         );  // copy/duplicate given tree (iterative)

Node *searchtree(Tree *, char   );  // find node in tree

Tree *grabnode_s(Tree *, Node **);  // stack-based grabnode
Tree *grabnode_r(Tree *, Node **);  // recursive grabnode
Tree *grabnode_i(Tree *, Node **);  // iterative grabnode

List *traverse_s(Tree *, char   );  // stack-based traverse (in mode)
List *traverse_r(Tree *, char   );  // recursive traverse (in mode)
List *traverse_i(Tree *, char   );  // iterative traverse (in mode)

Tree *rmtree    (Tree *         );  // purge and deallocate tree

Tree *balance   (Tree *         );  // rebalanced tree (root is midpoint)

void  print_tree(Tree *         );  // display tree structure (to STDOUT)

#endif