Binary tree using array

A binary tree can live in a single C array by placing nodes in level order (breadth-first, left to right on each level)—the same slot layout used by binary heaps. This page shows the indexing rules, how to code safe navigation in C, and when an array is a poor fit.

You already saw the big picture on Tree representation. Here we focus on binary trees only and on writing correct index arithmetic in C.

1) Level-order layout and indices

The root is at index 0. Children follow level by level. For any node at index i (with 0-based indexing):

Here n is the number of slots you treat as part of this tree—either the logical size after the last stored value, or the physical array length, depending on how you pack the data.

Worked example

        10
      /    \
     20     30
    /  \    /
   40  50  60

Index:  0   1   2   3   4   5
Value: 10  20  30  40  50  60

Right child of the root: index 2*0+2 = 2 → 30. Parent of the node at index 5: (5-1)/2 = 2 → 30.

2) How big must the array be?

• Complete binary tree with n nodes, no gaps in level order: you need exactly n elements in sequence—no wasted middle slots.
• General shape with gaps: you must reserve enough indices so that the deepest node’s index fits. A skewed tree (essentially a linked list) can force index 2h - 1 for height h in the worst case, so the array may need length on the order of 2h even though only h + 1 nodes exist.

So: arrays are attractive when the tree stays balanced or complete; they hurt when the tree is thin and deep.

3) Representing “missing” children

Two common patterns:

• Dense packing: only store complete (or nearly complete) trees; every index from 0 to n-1 is meaningful. Missing children are implied by tree height / problem rules.
• Sentinel value: pick a value that cannot occur as real data (often -1 or INT_MIN if keys are positive), or use a parallel bool array marking occupied slots. Any child index that lands outside the array or hits a sentinel is treated as no child.

4) C helpers (sketch)

Typical macros or inline functions keep mistakes in one place:

#include <limits.h>
#include <stdbool.h>

#define EMPTY INT_MIN   /* example sentinel */

static inline int parent(int i) { return (i - 1) / 2; }
static inline int left_child(int i)  { return 2 * i + 1; }
static inline int right_child(int i) { return 2 * i + 2; }

/* n = number of slots we consider (e.g. used length) */
static inline bool has_left(const int *t, int n, int i) {
    int j = left_child(i);
    return j < n && t[j] != EMPTY;
}
static inline bool has_right(const int *t, int n, int i) {
    int j = right_child(i);
    return j < n && t[j] != EMPTY;
}

Traversal orders from Tree traversal methods can be implemented with loops/recursion over indices (DFS) or with a queue for level order—same logic as pointer trees, but neighbors are found with arithmetic instead of ->left / ->right.

5) Complete C program (arrays only, no struct / pointers)

The program below uses a global tree[] and sentinel -1 for empty slots, insertRoot / insertLeft / insertRight, all three DFS traversals, a simple level-order print, search, update, delete, height, and leaf counts. Scroll the code block to read it in full.

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

#define MAX_SIZE 100

// Global arrays to store the binary tree
int tree[MAX_SIZE];  // Array to store node values (-1 means empty)
int size = 0;        // Current number of nodes in the tree

// Initialize the binary tree
void initTree() {
    size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        tree[i] = -1;  // -1 indicates empty node
    }
}

// Check if tree is full
int isFull() {
    return size >= MAX_SIZE;
}

// Check if tree is empty
int isEmpty() {
    return size == 0;
}

// Insert root node
void insertRoot(int value) {
    if (isFull()) {
        printf("Tree is full! Cannot insert root.\n");
        return;
    }
    if (tree[0] == -1) {
        tree[0] = value;
        size++;
        printf("Root node %d inserted at index 0\n", value);
    } else {
        printf("Root already exists at index 0 with value %d!\n", tree[0]);
    }
}

// Insert left child at given parent index
void insertLeft(int parentIndex, int value) {
    if (isFull()) {
        printf("Tree is full! Cannot insert left child.\n");
        return;
    }
    
    if (parentIndex >= MAX_SIZE || parentIndex < 0) {
        printf("Invalid parent index!\n");
        return;
    }
    
    if (tree[parentIndex] == -1) {
        printf("Parent node at index %d is empty! Insert parent first.\n", parentIndex);
        return;
    }
    
    int leftChildIndex = 2 * parentIndex + 1;
    if (leftChildIndex >= MAX_SIZE) {
        printf("Cannot insert left child - would exceed array bounds!\n");
        return;
    }
    
    if (tree[leftChildIndex] != -1) {
        printf("Left child already exists at index %d with value %d!\n", 
               leftChildIndex, tree[leftChildIndex]);
        return;
    }
    
    tree[leftChildIndex] = value;
    size++;
    printf("Left child %d inserted at index %d (parent: %d at index %d)\n", 
           value, leftChildIndex, tree[parentIndex], parentIndex);
}

// Insert right child at given parent index
void insertRight(int parentIndex, int value) {
    if (isFull()) {
        printf("Tree is full! Cannot insert right child.\n");
        return;
    }
    
    if (parentIndex >= MAX_SIZE || parentIndex < 0) {
        printf("Invalid parent index!\n");
        return;
    }
    
    if (tree[parentIndex] == -1) {
        printf("Parent node at index %d is empty! Insert parent first.\n", parentIndex);
        return;
    }
    
    int rightChildIndex = 2 * parentIndex + 2;
    if (rightChildIndex >= MAX_SIZE) {
        printf("Cannot insert right child - would exceed array bounds!\n");
        return;
    }
    
    if (tree[rightChildIndex] != -1) {
        printf("Right child already exists at index %d with value %d!\n", 
               rightChildIndex, tree[rightChildIndex]);
        return;
    }
    
    tree[rightChildIndex] = value;
    size++;
    printf("Right child %d inserted at index %d (parent: %d at index %d)\n", 
           value, rightChildIndex, tree[parentIndex], parentIndex);
}

// Get left child index
int getLeftChildIndex(int parentIndex) {
    return 2 * parentIndex + 1;
}

// Get right child index
int getRightChildIndex(int parentIndex) {
    return 2 * parentIndex + 2;
}

// Get parent index
int getParentIndex(int childIndex) {
    if (childIndex <= 0) return -1;
    return (childIndex - 1) / 2;
}

// Get left child value
int getLeftChild(int parentIndex) {
    int leftIndex = getLeftChildIndex(parentIndex);
    if (leftIndex < MAX_SIZE && tree[leftIndex] != -1) {
        return tree[leftIndex];
    }
    return -1;
}

// Get right child value
int getRightChild(int parentIndex) {
    int rightIndex = getRightChildIndex(parentIndex);
    if (rightIndex < MAX_SIZE && tree[rightIndex] != -1) {
        return tree[rightIndex];
    }
    return -1;
}

// Get parent value
int getParent(int childIndex) {
    int parentIndex = getParentIndex(childIndex);
    if (parentIndex >= 0 && tree[parentIndex] != -1) {
        return tree[parentIndex];
    }
    return -1;
}

// Inorder traversal (Left - Root - Right)
void inorderTraversal(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }
    
    inorderTraversal(getLeftChildIndex(index));
    printf("%d ", tree[index]);
    inorderTraversal(getRightChildIndex(index));
}

// Preorder traversal (Root - Left - Right)
void preorderTraversal(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }
    
    printf("%d ", tree[index]);
    preorderTraversal(getLeftChildIndex(index));
    preorderTraversal(getRightChildIndex(index));
}

// Postorder traversal (Left - Right - Root)
void postorderTraversal(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }
    
    postorderTraversal(getLeftChildIndex(index));
    postorderTraversal(getRightChildIndex(index));
    printf("%d ", tree[index]);
}

// Level order traversal (breadth-first)
void levelOrderTraversal() {
    if (isEmpty()) {
        printf("Tree is empty!\n");
        return;
    }
    
    printf("Level Order Traversal: ");
    for (int i = 0; i < MAX_SIZE; i++) {
        if (tree[i] != -1) {
            printf("%d ", tree[i]);
        }
    }
    printf("\n");
}

// Search for a value in the tree
int search(int value) {
    for (int i = 0; i < MAX_SIZE; i++) {
        if (tree[i] == value) {
            return i;  // Return index if found
        }
    }
    return -1;  // Not found
}

// Get node value at specific index
int getNodeValue(int index) {
    if (index >= 0 && index < MAX_SIZE) {
        return tree[index];
    }
    return -1;
}

// Update node value at specific index
void updateNode(int index, int value) {
    if (index >= 0 && index < MAX_SIZE && tree[index] != -1) {
        printf("Updating node at index %d from %d to %d\n", 
               index, tree[index], value);
        tree[index] = value;
    } else {
        printf("Invalid index or empty node!\n");
    }
}

// Delete a node (set to -1)
void deleteNode(int index) {
    if (index >= 0 && index < MAX_SIZE && tree[index] != -1) {
        printf("Deleting node at index %d with value %d\n", 
               index, tree[index]);
        tree[index] = -1;
        size--;
        
        // Optional: Also delete all children
        printf("Deleting all children of node at index %d as well...\n", index);
        deleteNode(getLeftChildIndex(index));
        deleteNode(getRightChildIndex(index));
    }
}

// Display the entire array representation
void displayTree() {
    printf("\n=== Binary Tree Array Representation ===\n");
    printf("Index: ");
    for (int i = 0; i < MAX_SIZE && i < size * 2; i++) {
        if (tree[i] != -1) {
            printf("%3d ", i);
        }
    }
    printf("\nValue: ");
    for (int i = 0; i < MAX_SIZE && i < size * 2; i++) {
        if (tree[i] != -1) {
            printf("%3d ", tree[i]);
        }
    }
    printf("\n");
    printf("Total nodes: %d\n", size);
    printf("Array size: %d\n", MAX_SIZE);
    printf("=======================================\n");
}

// Display tree in a tree-like format (limited to first few levels)
void displayTreeStructure() {
    printf("\n=== Tree Structure ===\n");
    if (isEmpty()) {
        printf("Tree is empty!\n");
        return;
    }
    
    printf("Level 0: %d\n", tree[0]);
    
    if (tree[1] != -1 || tree[2] != -1) {
        printf("Level 1: ");
        if (tree[1] != -1) printf("%d ", tree[1]);
        else printf("- ");
        if (tree[2] != -1) printf("%d ", tree[2]);
        else printf("-");
        printf("\n");
    }
    
    if (tree[3] != -1 || tree[4] != -1 || tree[5] != -1 || tree[6] != -1) {
        printf("Level 2: ");
        for (int i = 3; i <= 6; i++) {
            if (tree[i] != -1) printf("%d ", tree[i]);
            else printf("- ");
        }
        printf("\n");
    }
    
    if (tree[7] != -1 || tree[8] != -1 || tree[9] != -1 || tree[10] != -1 ||
        tree[11] != -1 || tree[12] != -1 || tree[13] != -1 || tree[14] != -1) {
        printf("Level 3: ");
        for (int i = 7; i <= 14; i++) {
            if (tree[i] != -1) printf("%d ", tree[i]);
            else printf("- ");
        }
        printf("\n");
    }
}

// Calculate height of the tree
int treeHeight(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return 0;
    }
    
    int leftHeight = treeHeight(getLeftChildIndex(index));
    int rightHeight = treeHeight(getRightChildIndex(index));
    
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Count total nodes (wrapper for size)
int countNodes() {
    return size;
}

// Count leaf nodes
int countLeafNodes(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return 0;
    }
    
    int leftIndex = getLeftChildIndex(index);
    int rightIndex = getRightChildIndex(index);
    
    if ((leftIndex >= MAX_SIZE || tree[leftIndex] == -1) &&
        (rightIndex >= MAX_SIZE || tree[rightIndex] == -1)) {
        return 1;  // This is a leaf node
    }
    
    return countLeafNodes(leftIndex) + countLeafNodes(rightIndex);
}

// Clear the entire tree
void clearTree() {
    initTree();
    printf("Tree has been cleared!\n");
}

// Main function with examples
int main() {
    printf("=== Binary Tree Implementation using Arrays (No Structures/Pointers) ===\n\n");
    
    // Initialize the tree
    initTree();
    
    // Example 1: Creating a simple tree
    printf("Example 1: Creating a simple binary tree\n");
    printf("Tree structure:\n");
    printf("        10\n");
    printf("       /  \\\n");
    printf("      5    15\n");
    printf("     / \\     \\\n");
    printf("    3   7     20\n\n");
    
    insertRoot(10);
    insertLeft(0, 5);
    insertRight(0, 15);
    insertLeft(1, 3);    // Index 1 is node 5
    insertRight(1, 7);   // Index 1 is node 5
    insertRight(2, 20);  // Index 2 is node 15
    
    printf("\n");
    displayTree();
    displayTreeStructure();
    
    printf("\n=== Traversals ===\n");
    printf("Inorder Traversal (Left-Root-Right): ");
    inorderTraversal(0);
    printf("\n");
    
    printf("Preorder Traversal (Root-Left-Right): ");
    preorderTraversal(0);
    printf("\n");
    
    printf("Postorder Traversal (Left-Right-Root): ");
    postorderTraversal(0);
    printf("\n");
    
    levelOrderTraversal();
    
    // Example 2: Searching
    printf("\n=== Searching ===\n");
    int searchValue = 7;
    int index = search(searchValue);
    if (index != -1) {
        printf("Value %d found at index %d\n", searchValue, index);
        printf("  - Parent value: %d at index %d\n", 
               getParent(index), getParentIndex(index));
        printf("  - Left child: %d at index %d\n", 
               getLeftChild(index), getLeftChildIndex(index));
        printf("  - Right child: %d at index %d\n", 
               getRightChild(index), getRightChildIndex(index));
    } else {
        printf("Value %d not found in tree\n", searchValue);
    }
    
    // Example 3: Tree properties
    printf("\n=== Tree Properties ===\n");
    printf("Tree height: %d\n", treeHeight(0));
    printf("Total nodes: %d\n", countNodes());
    printf("Leaf nodes: %d\n", countLeafNodes(0));
    
    // Example 4: Updating a node
    printf("\n=== Updating Node ===\n");
    updateNode(3, 8);  // Update node at index 3 from 3 to 8
    displayTree();
    
    // Example 5: Array index calculations
    printf("\n=== Array Index Calculation Demonstration ===\n");
    printf("For root node at index 0 (value: %d):\n", tree[0]);
    printf("  - Left child index: %d\n", getLeftChildIndex(0));
    printf("  - Right child index: %d\n", getRightChildIndex(0));
    printf("For node at index 2 (value: %d):\n", tree[2]);
    printf("  - Parent index: %d\n", getParentIndex(2));
    printf("  - Left child index: %d\n", getLeftChildIndex(2));
    printf("  - Right child index: %d\n", getRightChildIndex(2));
    
    // Example 6: Creating a complete binary tree
    printf("\n=== Example 2: Creating a complete binary tree ===\n");
    initTree();  // Reset tree
    
    printf("Creating a complete binary tree with values 1-7\n");
    printf("Structure:\n");
    printf("        1\n");
    printf("       / \\\n");
    printf("      2   3\n");
    printf("     / \\ / \\\n");
    printf("    4  5 6  7\n\n");
    
    int values[] = {1, 2, 3, 4, 5, 6, 7};
    insertRoot(values[0]);
    insertLeft(0, values[1]);
    insertRight(0, values[2]);
    insertLeft(1, values[3]);
    insertRight(1, values[4]);
    insertLeft(2, values[5]);
    insertRight(2, values[6]);
    
    printf("\nComplete Binary Tree Traversal:\n");
    printf("Inorder: ");
    inorderTraversal(0);
    printf("\nPreorder: ");
    preorderTraversal(0);
    printf("\nPostorder: ");
    postorderTraversal(0);
    printf("\n");
    levelOrderTraversal();
    
    printf("\nTree height: %d\n", treeHeight(0));
    printf("Number of leaf nodes: %d\n", countLeafNodes(0));
    
    // Example 7: Search in complete tree
    printf("\n=== Searching in Complete Tree ===\n");
    searchValue = 5;
    index = search(searchValue);
    if (index != -1) {
        printf("Found %d at index %d\n", searchValue, index);
        printf("Parent of %d is %d at index %d\n", 
               searchValue, getParent(index), getParentIndex(index));
    }
    
    // Example 8: Demonstration of array indices for sparse tree
    printf("\n=== Example 3: Creating a skewed tree ===\n");
    initTree();
    printf("Creating a right-skewed tree:\n");
    printf("10 -> 20 -> 30 -> 40\n\n");
    
    insertRoot(10);
    insertRight(0, 20);   // node 20 at index 2
    insertRight(2, 30);   // right child of index 2 → index 6
    insertRight(6, 40);   // right child of index 6 → index 14
    
    displayTree();
    printf("Inorder traversal of skewed tree: ");
    inorderTraversal(0);
    printf("\n");
    
    printf("\n=== Array Index Analysis for Skewed Tree ===\n");
    printf("Node 10 at index 0\n");
    printf("Node 20 at index 2 (right child of 0)\n");
    printf("Node 30 at index 6 (right child of index 2)\n");
    printf("Node 40 at index 14 (right child of index 6)\n");
    printf("Notice the exponential growth in indices!\n");
    
    return 0;
}

Key features (no structures / pointers)

1. Global arrays only: one tree[] for values and a size counter—no struct, no malloc.
2. Index-based: root at 0; left 2*i+1, right 2*i+2; parent (i-1)/2.
3. Operations: init, insert root/left/right, inorder/preorder/postorder, level-order scan, search, update, delete (with recursive child clear), helpers, height, leaf count, displays.
4. Interface: integer indices only—e.g. insertLeft(0, 5), inorderTraversal(0).

Sample output (excerpt)

=== Binary Tree Implementation using Arrays (No Structures/Pointers) ===

Example 1: Creating a simple binary tree
Tree structure:
        10
       /  \
      5    15
     / \     \
    3   7     20

Root node 10 inserted at index 0
Left child 5 inserted at index 1 (parent: 10 at index 0)
Right child 15 inserted at index 2 (parent: 10 at index 0)
Left child 3 inserted at index 3 (parent: 5 at index 1)
Right child 7 inserted at index 4 (parent: 5 at index 1)
Right child 20 inserted at index 6 (parent: 15 at index 2)

=== Binary Tree Array Representation ===
Index:   0   1   2   3   4   6 
Value:  10   5  15   3   7  20 
Total nodes: 6
=======================================

=== Tree Structure ===
Level 0: 10
Level 1: 5 15 
Level 2: 3 7 - 20 

=== Traversals ===
Inorder Traversal (Left-Root-Right): 3 5 7 10 15 20 
Preorder Traversal (Root-Left-Right): 10 5 3 7 15 20 
Postorder Traversal (Left-Right-Root): 3 7 5 20 15 10 
Level Order Traversal: 10 5 15 3 7 20 

The same program is available in the repo as binary-tree-array-demo.c. Compile with a C11 compiler, e.g. gcc -std=c11 binary-tree-array-demo.c -o tree_demo.

6) Binary heap vs binary tree in an array

Storage layout is the same (level order, same formulas). The difference is meaning:

• Heap: parent and children satisfy an order property (min-heap or max-heap) used for priority queues.
• Arbitrary binary tree: values have no heap constraint; the array is just a compact map of the shape.

7) When to use something else

If your tree grows unevenly or you insert/delete frequently, a linked representation usually wins. The next lesson covers that: Binary tree using linked list.