Seven numbers,
one binary tree,
counted in full.

A small program in C that builds a binary tree from an array of seven integers, then recursively counts its nodes. Below: the code, the tree, and the machinery in motion.

01 — The Program

Three functions, one purpose.

One function to build. One to count. One to orchestrate. Nothing else.

tree.c

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* create_tree(int arr[], int size) {
    if (size == 0) return NULL;

    struct Node** nodes = malloc(size * sizeof(struct Node*));
    for (int i = 0; i < size; i++) {
        nodes[i] = malloc(sizeof(struct Node));
        nodes[i]->data  = arr[i];
        nodes[i]->left  = NULL;
        nodes[i]->right = NULL;
    }
    for (int i = 0; i < size; i++) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < size) nodes[i]->left  = nodes[l];
        if (r < size) nodes[i]->right = nodes[r];
    }
    struct Node* root = nodes[0];
    free(nodes);
    return root;
}

int node_count(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + node_count(root->left)
             + node_count(root->right);
}

int main(void) {
    int arr[7] = {1, 2, 3, 4, 5, 6, 7};
    struct Node* root = create_tree(arr, 7);
    int count = node_count(root);
    printf("Number of nodes: %d\n", count);
    return 0;
}

$ gcc tree.c -o tree && ./tree

Number of nodes: 7

02 — The Walkthrough

Watch the recursion unfold.

Step through the program one call at a time. The tree on the left reflects what the stack is doing right now.

Call stack · grows upward depth 0

STEP 0 / 10

Ready to begin

main() is about to call create_tree with the array [1, 2, 3, 4, 5, 6, 7]. Press Play, or step through manually.

int arr[7] = {1, 2, 3, 4, 5, 6, 7}; struct Node* root = create_tree(arr, 7);

03 — The Ideas

What actually happened?

Three ideas do the heavy lifting in this tiny program.

— I

Array indexing as tree structure

A flat array becomes a tree by convention: the node at index i has children at indices 2i+1 and 2i+2. No pointer arithmetic is needed to find relatives — just a little math.

left = 2i+1 right = 2i+2

— II

Recursion meets its own base case

node_count calls itself on every child. The recursion stops when it hits NULL and returns 0. Every other call returns 1 plus whatever its children returned.

node_count(NULL) → 0

— III

The stack unwinds bottom-up

Deep calls finish first. Leaves return 1, their parents sum those up and return 3, and the root assembles the final 7. The answer is built on the way back.

1 + 3 + 3 = 7

Seven numbers,one binary tree,counted in full.