Question

How to parse a table into a binary tree in C

Answer 1

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

#define SIZE 100

typedef struct Node {
    int id;
    char name[64];
    struct Node* left;   // first child
    struct Node* right;  // next sibling
} Node;

/* -------------------- Print Tree -------------------- */

void printTree(Node* root, int depth) {
    if (!root) return;

    /* Print ROOT on its own line */
    if (depth == 0) {
        printf("ROOT\n");
    }

    /* Indent the node itself */
    for (int i = 0; i < depth + 1; ++i)
        printf("  ");

    /* print ID with leading zero if needed */
    printf("%02d - %s\n", root->id, root->name);

    /* first child */
    printTree(root->left, depth + 1);

    /* next sibling (another top-level node) */
    if (depth == 0 && root->right != NULL) {
        printTree(root->right, 0);   // restart ROOT
    } else {
        printTree(root->right, depth);
    }
}

/* -------------------- Build Tree -------------------- */

typedef struct {
    int id;
    char name[64];
    int parentId;
} Row;

Node* buildTree(const Row* table, int count, Node** nodesOut) {
    for (int i = 0; i < count; ++i) {
        nodesOut[table[i].id] = malloc(sizeof(Node));
        nodesOut[table[i].id]->id = table[i].id;
        strcpy(nodesOut[table[i].id]->name, table[i].name);
        nodesOut[table[i].id]->left = NULL;
        nodesOut[table[i].id]->right = NULL;
    }

    Node* root = NULL;

    for (int i = 0; i < count; ++i) {
        int id = table[i].id;
        int parentId = table[i].parentId;
        Node* current = nodesOut[id];

        if (parentId == 0) {
            if (!root) {
                root = current;
            } else {
                Node* p = root;
                while (p->right) p = p->right;
                p->right = current;
            }
        } else {
            Node* parent = nodesOut[parentId];
            if (!parent->left) {
                parent->left = current;
            } else {
                Node* p = parent->left;
                while (p->right) p = p->right;
                p->right = current;
            }
        }
    }

    return root;
}

/* -------------------- Main -------------------- */

int main(void) {
    Row table[] = {
       // Id  Name            ParentId 
        { 1, "Node 1",        0},
        { 2, "Node 1.1",      1},
        { 3, "Node 2",        0},
        { 4, "Node 1.1.1",    2},
        { 5, "Node 2.1",      3},
        { 6, "Node 2.3.1",    3},
        { 7, "Node 1.2",      1},
        { 8, "Node 1.3",      1},
        { 9, "Node 1.3.1",    8},
        {10, "Node 2.4",      3},
        {11, "Node 2.1.1",    5},
        {12, "Node 2.1.1.6", 11},
    };

    int count = sizeof(table) / sizeof(table[0]);
    Node** nodes = calloc(SIZE, sizeof(Node*));

    Node* root = buildTree(table, count, nodes);

    printTree(root, 0);

    for (int i = 0; i < SIZE; i++)
        free(nodes[i]);
    free(nodes);

    return 0;
}


/*
run:

ROOT
  01 - Node 1
    02 - Node 1.1
      04 - Node 1.1.1
    07 - Node 1.2
    08 - Node 1.3
      09 - Node 1.3.1
ROOT
  03 - Node 2
    05 - Node 2.1
      11 - Node 2.1.1
        12 - Node 2.1.1.6
    06 - Node 2.3.1
    10 - Node 2.4

*/

 

70+ SQL courses for beginners and professionals