Binary Tree traversal

Traversal of a binary tree is to access every node of binary tree at most once.

Breadth First :-

·        Level order

Depth First :-

•                  Pre order
•                   In order
•                 Post order

Pre order :-

<root>  <left>  <right>

In order :-

<left>  <root>  <right>

Post order:-

<left>  <right>  <root>


Pre order algorithm

1)visit root

2)visit left subtree

3)visit right subtree

typedef  struct  node

{

char data;

node *left;

node *right;

}node;

void preorder(node *root)

{

if(root==NULL)

return 1 ;

printf(“%c”,root->data);

preorder(root->data);

preoder(root->right);

}

void  inorder(node *root)

{

if(root==NULL)

          return 1;

inorder(root->left);

printf(“%c”,root->data);

inorder(root->right);

}

void postorder(node *root)

{

if(root==NULL)

          return 1;

postorder(root->left);

postorder(root->right);

printf(“%c”,root->data);

}


Time Complexity

O(n)