A binary tree is a nonlinear data structure that models hierarchical relationships between parent and child nodes, embodying the divide-and-conquer principle. Like linked lists, its fundamental unit is a node containing a value, a pointer to the left child, and a pointer to the right child.

// Node structure for a binary tree
typedef struct TreeNode {
    int data;
    int depth;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// Constructor function
TreeNode* createNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = value;
    node->depth = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Each node maintains two pointers: one to its left child and another to its right child. The node itself is considered the parent of these children. When examining a specific node in a binary tree, the subtree rooted at its left child and all descendants form the left subtree; similarly, the right subtree consists of the right child and its descendants. In a binary tree, non-leaf nodes always have at least one child and a non-empty subtree. For instance, if node 2 is treated as a parent, its left and right children are nodes 4 and 5, respectively, with their respective subtrees defined accordingly.

Key Terminology

• Root node: The topmost node with no parent.
• Leaf node: A node with no children—both pointers point to null.
• Edge: A connection between two nodes, represented by a pointer.
• Level: The level number increases from top to bottom, starting at 1 for the root.
• Degree: The number of children a node has. In a binary tree, this can be 0, 1, or 2.
• Height: The number of edges from the root to the farthest leaf.
• Depth: The number of edges from the root to a given node.
• Node height: The number of edges from the node to the farthest leaf.

Note: While most definitions count edges, some sources define height and depth as counting nodes. In such cases, add 1 to the edge-based result.

Core Operations

1. Initialize Binary Tree Similar to linked lists, initialize nodes first, then link them via pointers.

   // Initialize nodes
   TreeNode* n1 = createNode(1);
   TreeNode* n2 = createNode(2);
   TreeNode* n3 = createNode(3);
   TreeNode* n4 = createNode(4);
   TreeNode* n5 = createNode(5);
   
   // Establish links
   n1->left = n2;
   n1->right = n3;
   n2->left = n4;
   n2->right = n5;
   

2. Insert and Remove Nodes These operations modify pointers. Insertion may alter structural logic; deletion typically removes a node and its entire subtree.

   TreeNode* new_node = createNode(0);
   // Insert between n1 and n2
   n1->left = new_node;
   new_node->left = n2;
   // Delete new_node
   n1->left = n2;
   

Common Binary Tree Types

• Perfect Binary Tree: All levels are completely filled. Every non-leaf node has exactly two children. If height is h, total nodes are 2^(h+1) - 1. This reflects natural branching patterns like cell division.

• Complete Binary Tree: Only the last level may be incomplete, and nodes are filled from left to right.

• Full Binary Tree: Every node except leaves has exactly two children.

• Balanced Binary Tree: For every node, the absolute difference in heights of left and right subtrees is ≤ 1.

Degeneration of Binary Trees

An ideal binary tree has full layers. However, when all nodes lean toward one side, the structure degenerates into a linear chain resembling a linked list.

• Perfect trees represent optimal performance, enabling efficient divide-and-conquer strategies.
• Degenerated chains lead to O(n) time complexity for all operations, negating the benefits of tree structures.

Tree Traversal

Trees are inherently nonlinear, so traversal requires algorithms beyond simple iteration.

Level-Order Traversal

This breadth-first approach visits nodes layer by layer, from left to right. It uses a queue to manage the order of exploration.

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int* levelOrder(struct TreeNode* root, int* size) {
    struct TreeNode** queue = (struct TreeNode**)malloc(MAX_SIZE * sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    queue[rear++] = root;

    int* result = (int*)malloc(MAX_SIZE * sizeof(int));
    int index = 0;

    while (front < rear) {
        struct TreeNode* curr = queue[front++];
        result[index++] = curr->val;

        if (curr->left != NULL)
            queue[rear++] = curr->left;
        if (curr->right != NULL)
            queue[rear++] = curr->right;
    }

    *size = index;
    result = realloc(result, (*size) * sizeof(int));
    free(queue);

    return result;
}

• Time Complexity: O(n), each node visited once.
• Space Complexity: O(n), due to queue storage during traversal.

Depth-First Traversals

These include pre-order, in-order, and post-order traversals—each following a recursive pattern.

void preOrder(struct TreeNode* root, int* arr, int* idx) {
    if (!root) return;
    arr[(*idx)++] = root->val;
    preOrder(root->left, arr, idx);
    preOrder(root->right, arr, idx);
}

void inOrder(struct TreeNode* root, int* arr, int* idx) {
    if (!root) return;
    inOrder(root->left, arr, idx);
    arr[(*idx)++] = root->val;
    inOrder(root->right, arr, idx);
}

void postOrder(struct TreeNode* root, int* arr, int* idx) {
    if (!root) return;
    postOrder(root->left, arr, idx);
    postOrder(root->right, arr, idx);
    arr[(*idx)++] = root->val;
}

• Time Complexity: O(n)
• Space Complexity: O(n) due to recursion stack depth in worst case (e.g., skewed tree).

Array Representation of Binary Trees

Instead of using pointers, binary trees can be stored in arrays by mapping nodes via level-order indexing.

Representing Perfect Binary Trees

For perfect trees, the relationship between parent and children is deterministic:

• Left child index: 2*i + 1
• Right child index: 2*i + 2

This formula replaces pointer navigation.

General Case

For non-perfect trees, missing nodes must be explicitly encoded. Using a sentinel value (e.g., INT_MAX) allows reconstruction of the original structure.

int tree[] = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15};

Complete binary trees benefit greatly since missing nodes only appear at the end of the array.

Implementation Example

typedef struct {
    int* data;
    int length;
} ArrayTree;

int left_child(int i) { return 2*i + 1; }
int right_child(int i) { return 2*i + 2; }

int get_value(ArrayTree* t, int i) {
    if (i < 0 || i >= t->length) return INT_MAX;
    return t->data[i];
}

void dfs_traverse(ArrayTree* t, int i, char* mode, int* res, int* idx) {
    if (get_value(t, i) == INT_MAX) return;
    if (strcmp(mode, "pre") == 0) res[(*idx)++] = get_value(t, i);
    dfs_traverse(t, left_child(i), mode, res, idx);
    if (strcmp(mode, "in") == 0) res[(*idx)++] = get_value(t, i);
    dfs_traverse(t, right_child(i), mode, res, idx);
    if (strcmp(mode, "post") == 0) res[(*idx)++] = get_value(t, i);
}

Advantages and Limitations

• Pros: Cache-friendly, no pointer overhead, supports random access.
• Cons: Requires contiguous memory; inefficient for large or sparse trees; costly insertions/deletions.

Binary Search Tree (BST)

A BST satisfies:

• All values in the left subtree < root value < all values in the right subtree.
• Both left and right subtrees are also BSTs.

Operations

Search

Navigate based on comparisons:

• If target > current → go right
• If target < current → go left
• If equal → found

Time complexity: O(log n) on average; O(n) if unbalanced.

Insert

Find insertion point via search, then attach new node. Prevent duplicates.

Delete

Three cases:

• Leaf: remove directly.
• One child: replace with child.
• Two children: replace with inorder successor (smallest in right subtree).

After deletion, recursively delete the successor.

Ordered Property

In-order traversal yields sorted output—a key feature for applications requiring ordered data retrieval without sorting.

Performance Analysis

Operation	Unsorted Array	Binary Search Tree
Search	O(n)	O(log n)
Insert	O(1)	O(log n)
Delete	O(n)	O(log n)

Best-case performance assumes balanced tree. Worst case occurs when tree becomes linear.

Applications

• Indexing systems in databases.
• Efficient lookup mechanisms.
• Maintaining dynamic ordered data streams.

AVL Tree: Self-Balancing BST

Proposed by Adelson-Velsky and Landis (1962), AVL trees maintain balance through rotations after every insertion/deletion.

Core Concepts

• Node Height: Distance to deepest leaf (edges counted). Leaves have height 0; null nodes have height -1.
• Balance Factor: height(left) - height(right). Must satisfy -1 ≤ bf ≤ 1.

int getHeight(TreeNode* node) { return node ? node->height : -1; }
void updateHeight(TreeNode* node) {
    int lh = getHeight(node->left);
    int rh = getHeight(node->right);
    node->height = (lh > rh ? lh : rh) + 1;
}

int getBalanceFactor(TreeNode* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

Rotations

Used to restore balance after insertions/deletions:

• Right Rotation: Fixes left-heavy imbalance.
• Left Rotation: Fixes right-heavy imbalance.
• Double Rotations: Used when single rotation fails.

TreeNode* rotateRight(TreeNode* y) {
    TreeNode* x = y->left;
    TreeNode* T = x->right;
    x->right = y;
    y->left = T;
    updateHeight(y);
    updateHeight(x);
    return x;
}

TreeNode* rotateLeft(TreeNode* x) {
    TreeNode* y = x->right;
    TreeNode* T = y->left;
    y->left = x;
    x->right = T;
    updateHeight(x);
    updateHeight(y);
    return y;
}

Insert and Delete

After modifying the tree, traverse upward from the changed node, applying rotations as needed to restore balance.

Use Cases

• High-performance indexing.
• Databases with frequent lookups.
• Systems where predictable O(log n) guarantees are critical.

Despite higher rotation cost then red-black trees, AVL trees offer tighter balancing and faster searches in static environments.