Printing a binary search tree with commas and spaces in C

Admin 1
Viewed 127

I am struggling to print a binary search tree like the below output (in-order traversal):

2, 3, 6, 9

the output I get:

2, 3, 6, 9,

The code I have:

void inorder(struct node* root)
{   
    if (root != NULL) {
        inorder(root->left_node);
        printf("%d, ", root->value);
        inorder(root->right_node);
    }
     
}

how struct node is implemented:

struct node {
    int value;           
    struct node *left_node;  
    struct node *right_node; 

};

I am not sure how to get rid of the comma and the space characters after the last element.

binary-search-tree binary-search recursion printf c
2 Answers

The theory is that you have to print the , only if you are sure that the leaf you are printing is not the last one.

Thus, you need a way to tell your nodes (sub-trees) whether they contain the "last" leaf of your tree. One way of doing is to create another function which takes one more parameter:

static void inorder_haslastleaf(struct node* root, int haslastleaf) {
  if (root != NULL) {
    /* Print the left sub-tree, we are guaranteed it can't contain the last leaf
     * because the current node will be printed right after. */
    inorder_haslastleaf(root->left_node, 0);
    printf("%d", root->value);
    /* Now, we have to print comma if and only if we are sure that
     * some nodes will be printed after it. We can make sure of that
     * thanks to the haslastleaf flag. */
    if(!haslastleaf || root->right_node != NULL)
      printf(", ");
    /* Finally, print the right sub-tree. Pass back haslastleaf to it
     * to notify whether it contains the last leaf or not  */
    inorder_haslastleaf(root->right_node, haslastleaf);
  }
}

void inorder(struct node* root)
{
  /* Of course, the main tree contains the last leaf */
  inorder_haslastleaf(root, 1);
}
user_64797800

You only need to print a , if the right node is not null. With that in mind, split the printf() into two calls and check whether the next node is null or not.

void inorder(struct node* root)
{   
    if (root != NULL) {
        inorder(root->left_node);
        printf("%d", root->value);
        if (root->right_node)
             printf(", ");
        inorder(root->right_node);
    }         
}
Deathstick_590810
Related