Traversals of a Binary Tree

Write C code to implement the preorder(), inorder() and postorder() traversals. Whats their time complexities?

#include<stdio.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

void inorder_print(tree T)
{
if (T!=NULL)
{
printf("%d\n",T->data);
inorder_print(T->left);
inorder_print(T->right);
}
}

void postorder_print(tree T)
{
if (T==NULL)
{
return;
}
postorder_print(T->left);
postorder_print(T->right);
printf("%d\n",T->data);
}

void preorder_print(tree T)
{
if (T==NULL)
{
return;
}
printf("%d\n",T->data);
preorder_print(T->left);
preorder_print(T->right);

}


Each of them traverse all the nodes.
So the complexity is O(N).

Click Here For More Questions

2 comments:

  1. There is type in inorder_print function.

    ReplyDelete
  2. code for inorder recursive traversal needs some amendments.
    thanks

    ReplyDelete