Binary Search Tree Traversal implementation in C/C++

<syntaxhighlight lang="C" name="bst_traversal">

1. include <stdio.h>
2. include <stdlib.h>

struct node {

   int val;
   struct node * left;
   struct node * right;

}; typedef struct node node;

void insert(node ** root, int val) { if(*root == NULL)//Checking if tree is empty { *root = (node*) malloc(sizeof(node)); (*root) -> left = NULL; (*root) -> right = NULL; (*root) -> val = val; } else { node * trav = *root; while(1) { if(val < trav -> val)//value to be inserted is lesser than the node value { if(trav -> left == NULL) { insert(&trav->left, val);//inserting as a left child return; } else { trav = trav -> left; } } else if(val > trav -> val)//value to be inserted is greater than the node value { if(trav -> right == NULL) { insert(&trav->right, val);//Inserting as a right child return; } else { trav = trav -> right; } } else { printf("\n!!!!Duplicate value: not insertable!!!\n"); return; } } } }

void preorder(node* tree) { if(tree == NULL) return; printf(" %d ",tree->val); preorder(tree-> left); preorder(tree->right); } void inorder(node* tree) { if(tree == NULL) return; inorder(tree-> left); printf(" %d ",tree->val); inorder(tree->right); } void postorder(node* tree) { if(tree == NULL) return; postorder(tree-> left); postorder(tree->right); printf(" %d ",tree->val); }

int main() { node* tree = NULL; //Making root point to NULL to identify that it is empty int x; char str[20]; printf("Enter the numbers (. to stop): "); while(1) { scanf("%s",str); if(str[0] == '.') { break; } sscanf(str,"%d",&x); insert(&tree, x); }

 	printf("\n*********Inorder*********\n");

inorder(tree);

 	printf("\n*********Preorder*********\n");

preorder(tree);

 	printf("\n*********Postorder*********\n");

postorder(tree); printf("\n"); return 0; }

</syntaxhighlight>

Tweet