/*
 * binary_tree.h - Árbol Binario (incluye sección BST)
 *
 * Inspirado en "Data Structures and Algorithms Made Easy"
 * por Narasimha Karumanchi.
 *
 */

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <stdbool.h>

/* ===== ESTRUCTURA DE NODO ===== */
typedef struct _tree_node {
  int data;
  struct _tree_node *left;
  struct _tree_node *right;
} TreeNode;

/* ===== CREACIÓN ===== */

/* Crea un nuevo nodo con el dato especificado */
TreeNode *create_tree_node(int data);

/* ===== RECORRIDOS ===== */

/* Recorre en preorden (raíz, izquierda, derecha) */
void preorder(TreeNode *root);

/* Recorre en inorden (izquierda, raíz, derecha) */
void inorder(TreeNode *root);

/* Recorre en postorden (izquierda, derecha, raíz) */
void postorder(TreeNode *root);

/* Recorre por niveles (level-order, iterativo)
 * Nota: usar queue/cola
 */
void level_order(TreeNode *root);

/* ===== CONSULTAS ===== */

/* Devuelve el número de nodos del árbol (recursivo) */
int size_tree(TreeNode *root);

/* Devuelve la altura del árbol (recursivo). Árbol vacío = -1, hoja = 0 */
int height_tree(TreeNode *root);

/* Devuelve la cantidad de hojas del árbol (recursivo) */
int count_leaves(TreeNode *root);

/* Verifica si el árbol está vacío */
bool is_empty_tree(TreeNode *root);

/* Verifica si el nodo es una hoja (no tiene hijos) */
bool is_leaf(TreeNode *node);

/* ===== MODIFICACIÓN ===== */

/* Inserta como hijo izquierdo del nodo dado si está libre.
 * Retorna true si se insertó, false en caso contrario. */
bool attach_left(TreeNode *parent, int data);

/* Inserta como hijo derecho del nodo dado si está libre.
 * Retorna true si se insertó, false en caso contrario. */
bool attach_right(TreeNode *parent, int data);

/* ===== DESTRUCCIÓN ===== */

/* Libera toda la memoria del árbol (recursivo) */
void destroy_tree(TreeNode *root);

/* ===== OPERACIONES AVANZADAS ===== */

/* Genera el "espejo" del árbol (intercambia subárboles izq/der recursivamente).
 * Retorna la nueva raíz. */
TreeNode *mirror_tree(TreeNode *root);

/* =========================================================
 *            ÁRBOL BINARIO DE BÚSQUEDA (BST)
 * ========================================================= */

/* Inserta data respetando la propiedad del BST.
 * Retorna la nueva raíz (puede cambiar) */
TreeNode *bst_insert(TreeNode *root, int data);

/* Busca un valor en el BST. Retorna true si se encontró */
bool bst_search(TreeNode *root, int data);

/* Elimina un valor del BST, si existe. Retorna la nueva raíz */
TreeNode *bst_delete(TreeNode *root, int data);

/* Devuelve el nodo con el mínimo valor en el BST (o NULL si vacío) */
TreeNode *bst_find_min(TreeNode *root);

/* Devuelve el nodo con el máximo valor en el BST (o NULL si vacío) */
TreeNode *bst_find_max(TreeNode *root);

#endif // BINARY_TREE_H