BST.cpp

#include <iostream>
#include<stdlib.h> 
using namespace std;

struct node{
    int key;
    struct node *right,*left;
};

struct node* newNode(int item){
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->right = NULL;
    temp->left = NULL;
}

struct node* constructBST(struct node *head, int item){
    
    if(head == NULL) {
        return newNode(item);
    }
    if(head->key >= item){
        head->left = constructBST(head->left, item);
    }
    else if(head->key < item) {
        head->right = constructBST(head->right, item);
    }
    
    return head;
    
}

void printInorder(struct node *root){
    
    if(root == NULL) return;
    
    printInorder(root->left);
    
    cout<<root->key<<" ";
    
    printInorder(root->right);
}

void printPreorder(struct node *root){
    
    if(root == NULL) return;
    
    cout<<root->key<<" ";
    
    printPreorder(root->left);
    
    printPreorder(root->right);
}

void printPostorder(struct node *root){
    
    if(root == NULL) return;
    
    printPostorder(root->left);
    
    printPostorder(root->right);
    
    cout<<root->key<<" ";
}

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n,k;
	    cin>>n>>k;
	    int arr[n];
	    for(int i=0;i<n;i++){
	        cin>>arr[i];
	    }
	    struct node *root = newNode(arr[0]);
	    for(int i=1;i<n;i++){
	        constructBST(root, arr[i]);
	    }
	    
	    printInorder(root);
	    cout<<endl;
	    printPreorder(root);
	    cout<<endl;
	    printPostorder(root);
	}
	return 0;
}