Binary tree using linked list

In C, a binary tree is often stored as a collection of nodes: each node holds a value and two pointers—left and right. Missing children are simply NULL. This matches what you saw on Tree representation and pairs naturally with binary tree using array.

1) Node type and NULL children

A minimal binary tree node keeps the payload and links to subtrees:

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

left == NULL or right == NULL means “no child” on that side—no sentinels or index math. The only handle you need from outside is a root pointer (Node *root).

2) Creating and destroying nodes

• Create: allocate with malloc(sizeof(Node)), set data, set left and right to NULL, then attach the node under its parent.
• Free: use a post-order walk—free left subtree, right subtree, then the current node—so you never dereference a pointer after free. The demo uses freeTree that follows that pattern.

3) Traversals (same logic as Tree traversal methods)

Replace “index arithmetic” with pointer chasing:

• DFS: inorder / preorder / postorder recurse on root->left and root->right, stopping at NULL.
• BFS (level order): use a queue of Node *—for teaching code, a small circular array of pointers works well; dequeue a node, print it, enqueue non-NULL children.

4) Tiny picture

  root ──► [ 10 ]
            /      \
          ▼          ▼
       [ 5 ]       [ 15 ]
       /   \           \
      ▼     ▼           ▼
   [...]  [...]       [...]

Each box is a struct in the heap; arrows are pointer fields—not array indices.

5) Complete C program (structs and pointers)

The program below builds the same logical trees as binary tree using array (sample tree, complete 1–7, right-skewed chain): create nodes, traverse, search, counts, level order with a fixed-size queue, and freeTree. Download binary-tree-linkedlist-demo.c and compile with gcc -std=c11 binary-tree-linkedlist-demo.c -o tree_ll_demo.

// Binary tree — linked representation (struct + left/right pointers).
// Same example shapes as binary-tree-array-demo.c for easy comparison.
// Compile: gcc -std=c11 binary-tree-linkedlist-demo.c -o tree_ll_demo

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

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

// ---------- Memory helpers ----------

Node *createNode(int data) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (n == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->left = n->right = NULL;
    return n;
}

// Post-order free: safe for arbitrary binary tree
void freeTree(Node *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// ---------- Metrics ----------

int treeHeight(Node *root) {
    if (root == NULL) {
        return 0;
    }
    int lh = treeHeight(root->left);
    int rh = treeHeight(root->right);
    return (lh > rh ? lh : rh) + 1;
}

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

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

Node *search(Node *root, int value) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == value) {
        return root;
    }
    Node *t = search(root->left, value);
    if (t != NULL) {
        return t;
    }
    return search(root->right, value);
}

// ---------- Depth-first traversals ----------

void inorder(Node *root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void preorder(Node *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void postorder(Node *root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

// Level order: array-based queue of Node * (simple, fixed cap)

#define QUEUE_CAP 512

void levelOrder(Node *root) {
    if (root == NULL) {
        printf("(empty tree)\n");
        return;
    }
    Node *q[QUEUE_CAP];
    int front = 0, rear = 0;
    q[rear++] = root;
    while (front < rear) {
        Node *cur = q[front++];
        printf("%d ", cur->data);
        if (cur->left != NULL) {
            q[rear++] = cur->left;
        }
        if (cur->right != NULL) {
            q[rear++] = cur->right;
        }
    }
}

// Build the “textbook” example tree (same as array demo):
// root 10; children 5 (left), 15 (right); 3,7 under 5; 20 under 15 (right).

Node *buildExampleTree(void) {
    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->right = createNode(20);
    return root;
}

// Complete tree with values 1..7 (full last level).

Node *buildCompleteTree(void) {
    Node *r = createNode(1);
    r->left = createNode(2);
    r->right = createNode(3);
    r->left->left = createNode(4);
    r->left->right = createNode(5);
    r->right->left = createNode(6);
    r->right->right = createNode(7);
    return r;
}

// Right-skewed chain 10 -> 20 -> 30 -> 40 (only right pointers)

Node *buildSkewedRight(void) {
    Node *r = createNode(10);
    r->right = createNode(20);
    r->right->right = createNode(30);
    r->right->right->right = createNode(40);
    return r;
}

// ---------- Main demos ----------

int main(void) {
    printf("=== Binary tree (linked list / pointer representation) ===\n\n");

    printf("Example 1: sample tree (same logical shape as array demo)\n");
    Node *t1 = buildExampleTree();
    printf("Inorder:    ");
    inorder(t1);
    printf("\nPreorder:   ");
    preorder(t1);
    printf("\nPostorder:  ");
    postorder(t1);
    printf("\nLevel order:");
    levelOrder(t1);
    printf("\n");

    printf("Height: %d | Nodes: %d | Leaves: %d\n",
           treeHeight(t1), countNodes(t1), countLeaves(t1));

    Node *hit = search(t1, 7);
    if (hit != NULL) {
        printf("Found value 7 at node %p (data=%d)\n", (void *)hit, hit->data);
    }

    printf("\nExample 2: complete binary tree (values 1..7)\n");
    freeTree(t1);
    Node *t2 = buildCompleteTree();
    printf("Level order: ");
    levelOrder(t2);
    printf("\nHeight: %d | Leaves: %d\n", treeHeight(t2), countLeaves(t2));
    freeTree(t2);

    printf("\nExample 3: right-skewed chain — no wasted array slots\n");
    Node *t3 = buildSkewedRight();
    printf("Inorder (chain): ");
    inorder(t3);
    printf("\nNodes: %d | Height: %d\n", countNodes(t3), treeHeight(t3));
    freeTree(t3);

    printf("\nDone.\n");
    return 0;
}

6) Array vs linked (binary tree)

7) What’s next

Concrete insert/delete APIs and edge cases were introduced in Binary tree operations (earlier in this track). For ordered search trees, continue to the BST lessons.