DS – BST Traversal

Traversal: We can traverse the binary search tree in 3 ways

• In order traversal
• Pre order traversal
• Post order traversal

For example,

Consider the BST with node representation:

Inorder traversal:

void print_inorder(){             if(root)                         inorder(root);             else                         print(“Empty BST”); } void inorder(struct Node *p){             if(p->left)                         inorder(p->left);               printf(“%d “, p->data);               if(p->right)                         inorder(p->right); }

Pre-order traversal:

void print_preorder(){             if(root)                         preorder(root);             else                         print(“Empty BST”); } void preorder(struct Node *p) {             printf(“%d “, p->data);                         if(p->left)                         preorder(p->left);               if(p->right)                         preorder(p->right); }

Postorder traversal:

void print_postorder() {             if(root)                         postorder(root);             else                         print(“Empty BST”); } void postorder(struct Node *p) {                       if(p->left)                         postorder(p->left);               if(p->right)                         postorder(p->right);               printf(“%d “, p->data); }