Core Tree Terminology

• Node Degree: The number of subtrees rooted at a node is defined as its degree.
• Leaf Node (Terminal Node): Nodes with a degree of 0 are classified as leaf nodes.
• Branch Node (Non-Terminal Node): Any node with a degree greater than 0 is a branch node.
• Parent Node: A node that contains child nodes is the parent of its direct children.
• Child Node: The root of a subtree belonging to a parent node is the child of that parent.
• Sibling Nodes: Nodes that share the same parent are siblings to each other.
• Tree Degree: The maximum node degree across all nodes in the entire tree is the tree's degree.
• Node Level: The root node is defined as level 1, its children are level 2, and levels increment downward from there.
• Tree Height (Depth): The maximum node level in the tree is the tree's height or depth.
• Cousin Nodes: Nodes whose parents reside on the same level are called cousins.
• Ancestor Node: All nodes along the path from the root to a given node are ancestors of that node.
• Descendant: Any node in the subtree rooted at a given node is a descendant of that node.
• Forest: A collection of m (m > 0) disjoint trees is called a forest.

Common general tree representation (child-sibling linked structure):

typedef int TreeData;
struct TreeNode
{
    struct TreeNode* firstChild;
    struct TreeNode* nextSibling;
    TreeData value;
};

Binary Trees: A Specialized Tree Type

Binary trees are trees where each node can have at most 2 children. There are two special categories of binary trees:

1. Full Binary Tree: A binary tree where every level contains the maximum possible number of nodes. A full binary tree with depth k has exactly 2^k - 1 total nodes.
2. Complete Binary Tree: A binary tree where every node maps one-to-one to the first n nodes of a depth k full binary tree (numbered top-to-bottom, left-to-right). Full binary trees are a special case of complete binary trees, and complete binary trees are highly efficient data structures.

Binary Tree Core Properties

1. For a non-empty binary tree with root at level 1, the maximum number of nodes on level h is 2^(h-1).
2. The maximum total number of nodes in a depth h binary tree is 2^h - 1.
3. For any non-empty binary tree, if X is the count of leaf nodes (degree 0) and Y is the count of nodes with degree 2, the relation X = Y + 1 always holds.
4. The depth of a full binary tree with n nodes is h = log2(n + 1).
5. For a complete binary tree with n nodes, numbreed 0 from root in array order, for any node at index i:
   • If i > 0, the parent of i is at index (i-1)/2; the root at i=0 has no parent.
   • If 2i + 1 < n, the left child of i is at 2i + 1, otherwise no left child exists.
   • If 2i + 2 < n, the right child of i is at 2i + 2, otherwise no right child exists.

Heaps: Specialized Complete Binary Trees

Heaps are a restricted variant of complete binary trees with two core properties:

1. The value of any node is always greater than or equal to or less than or equal to the value of its parent node.
2. All heaps are complete binary trees by definition.

Heaps are categorized into two types:

• Min-heap: Every parent node has a value less than or equal to its children.
• Max-heap: Every parent node has a value greater than or equal to its children.

Common Heap Applications

Heap Sort

Heap sort follows two core steps:

1. Heap construction: Build a max-heap for ascending sort, build a min-heap for descending sort.
2. Sort extraction: Repeatedly extract the root (the maximum/minimum element) and adjust the remaining heap to maintain heap properties. Downward adjustment is the core operation for both construction and deletion.

Linked Binary Tree Implementation

A binary tree is recursively defined as either an empty tree, or a root node plus sepaarte left and right binary subtrees. Below is a common linked implementation:

typedef int BTData;
typedef struct BinaryTreeNode
{
    BTData val;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

// Allocate a new tree node
BTNode* createNode(int val)
{
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL)
    {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    newNode->val = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Build binary tree from pre-order array with # as null sentinel
BTNode* buildFromPreorder(BTData* arr, int totalSize, int* currentIndex)
{
    if (arr[*currentIndex] == '#')
    {
        (*currentIndex)++;
        return NULL;
    }
    BTNode* currentNode = createNode(arr[(*currentIndex)++]);
    currentNode->left = buildFromPreorder(arr, totalSize, currentIndex);
    currentNode->right = buildFromPreorder(arr, totalSize, currentIndex);
    return currentNode;
}

// Manually construct a sample binary tree
BTNode* buildSampleTree()
{
    BTNode* n1 = createNode(1);
    BTNode* n2 = createNode(2);
    BTNode* n3 = createNode(3);
    BTNode* n4 = createNode(4);
    BTNode* n5 = createNode(5);
    BTNode* n6 = createNode(6);
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
    return n1;
}

// Pre-order traversal
void preOrder(BTNode* root)
{
    if (root == NULL) return;
    printf("%d ", root->val);
    preOrder(root->left);
    preOrder(root->right);
}

// In-order traversal
void inOrder(BTNode* root)
{
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->val);
    inOrder(root->right);
}

// Post-order traversal
void postOrder(BTNode* root)
{
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->val);
}

// Destroy entire binary tree
void destroyTree(BTNode* root)
{
    if (root == NULL) return;
    destroyTree(root->left);
    destroyTree(root->right);
    free(root);
}

// Count total number of nodes
int countNodes(BTNode* root)
{
    return root == NULL ? 0 : countNodes(root->left) + countNodes(root->right) + 1;
}

// Count number of leaf nodes
int countLeaves(BTNode* root)
{
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

// Count number of nodes on level k
int countLevelK(BTNode* root, int k)
{
    if (root == NULL) return 0;
    if (k == 1) return 1;
    return countLevelK(root->left, k - 1) + countLevelK(root->right, k - 1);
}

// Search for node with value x
BTNode* searchNode(BTNode* root, BTData x)
{
    if (root == NULL) return NULL;
    if (root->val == x) return root;
    BTNode* result = searchNode(root->left, x);
    return result != NULL ? result : searchNode(root->right, x);
}

// Level order traversal (requires pre-defined Queue implementation)
void levelOrder(BTNode* root)
{
    Queue q;
    queueInit(&q);
    if (root != NULL) queueEnqueue(&q, root);
    while (!queueIsEmpty(&q))
    {
        BTNode* curr = queueFront(&q);
        queueDequeue(&q);
        printf("%d ", curr->val);
        if (curr->left != NULL) queueEnqueue(&q, curr->left);
        if (curr->right != NULL) queueEnqueue(&q, curr->right);
    }
    queueDestroy(&q);
}

// Check if binary tree is complete
bool isCompleteTree(BTNode* root)
{
    if (root == NULL) return true;
    Queue q;
    queueInit(&q);
    queueEnqueue(&q, root);
    bool seenNull = false;
    while (!queueIsEmpty(&q))
    {
        BTNode* curr = queueFront(&q);
        queueDequeue(&q);
        if (curr == NULL)
        {
            seenNull = true;
            continue;
        }
        if (seenNull)
        {
            queueDestroy(&q);
            return false;
        }
        queueEnqueue(&q, curr->left);
        queueEnqueue(&q, curr->right);
    }
    queueDestroy(&q);
    return true;
}

Heap Array-Based Implementation

typedef int HeapData;
typedef struct {
    HeapData* arr;
    int size;
    int capacity;
} Heap;

// Helper swap function
void swap(HeapData* a, HeapData* b)
{
    HeapData temp = *a;
    *a = *b;
    *b = temp;
}

// Upward adjustment for min-heap
void adjustUp(HeapData* heapArr, int totalSize)
{
    int childIdx = totalSize - 1;
    int parentIdx = (childIdx - 1) / 2;
    while (parentIdx >= 0 && heapArr[parentIdx] > heapArr[childIdx])
    {
        swap(&heapArr[parentIdx], &heapArr[childIdx]);
        childIdx = parentIdx;
        parentIdx = (childIdx - 1) / 2;
    }
}

// Downward adjustment for max-heap
void adjustDownMax(HeapData* heapArr, int totalSize, int parentIdx)
{
    int childIdx = 2 * parentIdx + 1;
    while (childIdx < totalSize)
    {
        // Select the larger of the two children
        if (childIdx + 1 < totalSize && heapArr[childIdx + 1] > heapArr[childIdx])
        {
            childIdx++;
        }
        if (heapArr[childIdx] > heapArr[parentIdx])
        {
            swap(&heapArr[childIdx], &heapArr[parentIdx]);
            parentIdx = childIdx;
            childIdx = 2 * parentIdx + 1;
        }
        else break;
    }
}

// Downward adjustment for min-heap
void adjustDownMin(HeapData* heapArr, int totalSize, int parentIdx)
{
    int childIdx = 2 * parentIdx + 1;
    while (childIdx < totalSize)
    {
        // Select the smaller of the two children
        if (childIdx + 1 < totalSize && heapArr[childIdx + 1] < heapArr[childIdx])
        {
            childIdx++;
        }
        if (heapArr[childIdx] < heapArr[parentIdx])
        {
            swap(&heapArr[childIdx], &heapArr[parentIdx]);
            parentIdx = childIdx;
            childIdx = 2 * parentIdx + 1;
        }
        else break;
    }
}

// Initialize empty heap
void heapInit(Heap* hp)
{
    hp->arr = NULL;
    hp->size = hp->capacity = 0;
}

// Destroy heap
void heapDestroy(Heap* hp)
{
    assert(hp);
    free(hp->arr);
    hp->arr = NULL;
    hp->size = hp->capacity = 0;
}

// Get current heap size
int heapSize(Heap* hp)
{
    return hp->size;
}

// Check if heap is empty
bool heapIsEmpty(Heap* hp)
{
    return heapSize(hp) == 0;
}

// Get top (root) value of heap
HeapData heapTop(Heap* hp)
{
    assert(hp->size > 0);
    return hp->arr[0];
}

// Insert new value into min-heap
void heapPush(Heap* hp, HeapData val)
{
    if (hp->size == hp->capacity)
    {
        int newCap = hp->capacity == 0 ? 4 : hp->capacity * 2;
        HeapData* temp = (HeapData*)realloc(hp->arr, sizeof(HeapData) * newCap);
        if (temp == NULL)
        {
            perror("realloc failed");
            exit(EXIT_FAILURE);
        }
        hp->arr = temp;
        hp->capacity = newCap;
    }
    hp->arr[hp->size++] = val;
    adjustUp(hp->arr, hp->size);
}

// Remove root element from min-heap
void heapPop(Heap* hp)
{
    swap(&hp->arr[0], &hp->arr[hp->size - 1]);
    hp->size--;
    adjustDownMin(hp->arr, hp->size, 0);
}

// Heap sort for descending order (uses min-heap)
void heapSortDescending(int* arr, int size)
{
    // Build min-heap
    for (int i = 1; i <= size; i++)
    {
        adjustUp(arr, i);
    }
    // Extract elements to get descending order
    int end = size - 1;
    while (end > 0)
    {
        swap(&arr[0], &arr[end]);
        adjustDownMin(arr, end, 0);
        end--;
    }
}

// Heap sort for ascending order (uses max-heap)
void heapSortAscending(int* arr, int size)
{
    // Build max-heap
    for (int i = (size - 2) / 2; i >= 0; i--)
    {
        adjustDownMax(arr, size, i);
    }
    // Extract elements to get ascending order
    int end = size - 1;
    while (end > 0)
    {
        swap(&arr[0], &arr[end]);
        adjustDownMax(arr, end, 0);
        end--;
    }
}