Print tree node and all of it's childs efficiently

Question

I am trying to make a function that would print a node and all of its children but I am trying to make it efficient and also recursive. But it doesn't really work.

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

#define SIZE    100

typedef struct tree {
    int value;
    struct tree *child, *sibling, *parent;
} *Tree;

Tree initTree(int value) {
    Tree root = malloc(sizeof(struct tree));
    root->value = value;
    root->parent = NULL;
    root->child = NULL;
    root->sibling = NULL;
    return root;
}

void drawTreeHelper(Tree tree, FILE* stream) {
    Tree tmp;
    if (tree == NULL) {
        return;
    }
    fprintf(stream, "    %ld[label=\"%d\", fillcolor=red]\n", (intptr_t) tree, tree->value);
    tmp = tree->child;

    while (tmp != NULL) {
        fprintf(stream, "    %ld -> %ld \n", (intptr_t) tree, (intptr_t) tmp);
        drawTreeHelper(tmp, stream);
        tmp = tmp->sibling;
    }
}

void drawTree(Tree tree, char *fileName) {
    FILE* stream = fopen("test.dot", "w");
    char buffer[SIZE];
    fprintf(stream, "digraph tree {\n");
    fprintf(stream, "    node [fontname=\"Arial\", shape=circle, style=filled, fillcolor=yellow];\n");
    if (tree == NULL)
        fprintf(stream, "\n");
    else if (!tree->child)
        fprintf(stream, "    %ld [label=\"%d\"];\n", (intptr_t) tree, tree->value);
    else
        drawTreeHelper(tree, stream);
    fprintf(stream, "}\n");
    fclose(stream);
    sprintf(buffer, "dot test.dot | neato -n -Tpng -o %s", fileName);
    system(buffer);
}

Tree uniteTries(Tree child, Tree parent)
{
    if (parent)
    {
        if (!parent->child) parent->child = child;
        else
        {
            Tree iter = parent->child;
            while (iter->sibling) iter = iter->sibling;
            iter->sibling = child;
        }
    }
    return parent;
}

Tree uniteForest(Tree root, Tree *forest, int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        if (forest[i]) root = uniteTries(forest[i], forest[i]->parent);
    }
    root = forest[0];
    return root;
}

void printParentChildRec(Tree root)
{
    if(!root) return;
    printf("%d ", root->value);

    printParentChildRec(root->sibling);
    printParentChildRec(root->child);
}

int main() {
    int i;
    char buffer[SIZE];
    Tree *forest = malloc(6 * sizeof(Tree));
    for (i = 0; i < 6; i++) {
        forest[i] = initTree(i);
    }

    forest[1]->parent = forest[0];
    forest[2]->parent = forest[0];
    forest[3]->parent = forest[0];
    forest[4]->parent = forest[1];
    forest[5]->parent = forest[1];

    Tree root = uniteForest(root, forest, 6);

    printParentChildRec(root);

    drawTree(root, "tree.png");

    return 0;
}

This code will provide you with a verifiable example and here's what I tried to do:

void printParentChildRec(Tree root) {
    if (!root)
        return;
    printf("%d ", root->value);

    printParentChildRec(root->sibling);
    printParentChildRec(root->child);
}

The results I am getting is just 0 1 2 3 4 5 which is all the nodes, but I want to print something like this:

0 1 2 3
1 4 5
2
3
4
5

Answer 1

There are some problems in your code:

• You hide pointers behind typedefs, this is confusing for readers of your code and often leads to programming errors.
• You print intptr_t values with %ld, which is undefined behavior on platforms where intptr_t is not an alias for long and has a different size, such as Windows 64-bit. There is no specific printf format for this type, you should either recast the value as (long)(intptr_t)tree or (long long)(intptr_t)tree and use %lld, or their unsigned versions or use the %p format with (void *)tree.
• the result you expect is not produced as text, but some form of graphics rendering which is difficult to analyse from the code. Producing textual output first would be easier to debug.

Here are more problems in your code:

• in main(), Tree root = uniteForest(root, forest, 6); passes undefined variable root to uniteForest.

• argument root in Tree uniteForest(Tree root, Tree *forest, int n) is never used, it is used only to store temporary results. You should just remove the argument and simplify the code as:

  Tree uniteForest(Tree *forest, int n) {
      for (int i = 0; i < n; i++) {
          if (forest[i])
              uniteTries(forest[i], forest[i]->parent);
      }
      return forest[0];
  }
  

• main only prints the root of the tree, hence the value of forest[0] and those of its descendants recursively. You instead want to print the value of the node and that of its immediate children, then recurse for each child.

Here is a corrected version:

void printParentChildRec(Tree node) {
    if (node) {
        printf("%d ", node->value);
        for (Tree child = node->child; child; child = child->sibling) {
            printf("%d ", child->value);
        }
        printf("\n");
        for (Tree child = node->child; child; child = child->sibling) {
            printParentChildRec(child);
        }
    }
}

Output:

0 1 2 3
1 4 5
4
5
2
3

Answer 2

I think your unite trees function is the problem here. I ran this code with my debugger and this is what it looks like from the root

This is the root as inputted into the print function after the unite trees method:

Can you tell me what you are trying to achieve here and maybe I can help you out!