CODEWITHSUNDEEP
cbinary-search-treetree-traversalpreorderpostorder
Diwakar Sharma
Diwakar Sharma

Reputation: 425

tree traversal not giving expected output

I have this below simple code which is standard I believe for traversal. The problem is I'm getting expected output for a particular set of input, and unexpected for other. e.g. for input sequence 15,3,6,11,45,54,65,3,66 I am getting as expected pre-order o/p : 15,3,6,11,45,54,65,66. But for sequence 45,3,54,65,23,66,5,3 I expect pre-order o/p 45,3,23,5,54,65,66 but I'm getting 45 3 5 23 54 65 66. For post-order, I get unexpected for both the sequences, getting 3,6,11,45,54,65,66,15 and 3,5,23,54,65,66,45 while I expect 11,6,3,66,65,54,45,15 and 5,23,3,66,65,54,45 respectively. Am I understanding it incorrectly or is there some problem with my code?

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

typedef struct treenode
{
  int val;
  struct treenode *left;
  struct treenode *right;
} bnode;

bnode *rootnd = NULL;

bnode * ins_node(bnode *bootstrap, bnode *newnode)
{
  if (bootstrap == NULL )
  {
    bootstrap = newnode;
  }
  else if (newnode->val < bootstrap->val)
    bootstrap->left = ins_node(bootstrap->left, newnode);
  else if (newnode->val > bootstrap->val)
    bootstrap->right = ins_node(bootstrap->right, newnode);

  return bootstrap;
}

void print_tree_inorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left);
    printf("%d ", root->val);
    print_tree_inorder(root->right);
  }
}

void print_tree_postorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left);
    print_tree_inorder(root->right);
    printf("%d ", root->val);
  }
}

void print_tree_preorder(bnode *root)
{
  if (root != NULL )
  {
    printf("%d ", root->val);
    print_tree_inorder(root->left);
    print_tree_inorder(root->right);
  }
}

int main(int argc, char *argv[])
{
  int insval;

  printf("Keep entering numbers... press 0 to finish\n");

  while (1)
  {
    scanf("%d", &insval);

    if (insval == 0)
      break;

    bnode *nd = malloc(sizeof(bnode));
    nd->val = insval;
    nd->left = NULL;
    nd->right = NULL;

    if (rootnd == NULL )
    {
      rootnd = nd;
    }
    else
      ins_node(rootnd, nd);
  }

  if (atoi(argv[1]) == 1)
    print_tree_preorder(rootnd);
  else if (atoi(argv[1]) == 2)
    print_tree_inorder(rootnd);
  else
    print_tree_postorder(rootnd);

  return 0;
}

Upvotes: 0

Views: 77

Answers (1)

Charlie Burns
Charlie Burns

Reputation: 7044

Your routines don't call themselves recursively as they should. See comments in the code below.

void print_tree_inorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left);
    printf("%d ", root->val);
    print_tree_inorder(root->right);
  }
}

void print_tree_postorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left); // should be print_tree_postorder
    print_tree_inorder(root->right); // same
    printf("%d ", root->val);
  }
}

void print_tree_preorder(bnode *root)
{
  if (root != NULL )
  {
    printf("%d ", root->val);
    print_tree_inorder(root->left); // should be print_tree_preorder
    print_tree_inorder(root->right); // ditto
  }
}

Upvotes: 1

Related Questions