Recursive and Iterative implementation of Preorder Inorder Postorder traversal of Binary Search Tree(BST)

BST_inorder_preorder_postorder_iterative.cpp

/*
Sample Input
10
5 4 8 1 6 10 3 7 2 9

Sample Output
PreOrder Recursive : 
5 4 1 3 2 8 6 7 10 9 
PreOrder iterative : 
5 4 1 3 2 8 6 7 10 9 

Inorder Recursive : 
1 2 3 4 5 6 7 8 9 10 
Inorder Iterative :
1 2 3 4 5 6 7 8 9 10 

PostOrder Recursive : 
2 3 1 4 7 6 9 10 8 5 
PostOrder Iterative :
2 3 1 4 7 6 9 10 8 5 
*/

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left;
    Node *right;
    
    Node (int x) {
        data = x;
        left = right = NULL;
    }
};

int N;

int main() {
    cin >> N;
    Node *root = NULL;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        
        function < Node* (Node*, int) > insertNode;
        insertNode = [&insertNode](Node *root, int x) {
            if (root == NULL) {
                Node *newNode = new Node(x);
                root = newNode;
                return root;
            } else if (x < root->data) root->left = insertNode(root->left, x);
            else if (x > root->data) root->right = insertNode(root->right, x);
            return root;
        };
        
        root = insertNode(root, x);
    }
    
    cout << "PreOrder Recursive : " << endl;
    
    auto PreOrder = [&](auto &self, Node *root) -> void {
        if (root == NULL) return ;
        cout << root->data << ' ';
        self(self, root->left);
        self(self, root->right);
    };
    
    PreOrder(PreOrder, root);
    cout << '\n';
    
    cout << "PreOrder iterative : " << endl;
    stack < Node* > s;
    s.push(root);
    
    while (!s.empty()) {
        Node *head = s.top();
        s.pop();
        cout << head->data << " ";
        if (head->right) s.push(head->right);
        if (head->left) s.push(head->left);
    }
    
    cout << '\n' << '\n';
    
    cout << "Inorder Recursive : " << endl;
    
    auto Inorder = [&](auto &self, Node *root) -> void {
        if (root == NULL) return ;
        self(self, root->left);
        cout << root->data << ' ';
        self(self, root->right);
    };
    
    Inorder(Inorder, root);
    cout << '\n';
    
    cout << "Inorder Iterative :" << endl;
    vector < int > visited(100, false);
    s.push(root);
    visited[root->data] = true;
    while (!s.empty()) {
        Node *head = s.top();
        if (head->left) {
            if (!visited[head->left->data]) {
                s.push(head->left);
                continue;
            }
        }
        visited[head->data] = true;
        cout << head->data << ' ';
        s.pop();
        if (head->right) {
            if (!visited[head->right->data]) {
                s.push(head->right);
                continue;
            }
        }
    }
    
    cout << '\n' << '\n';
    
    cout << "PostOrder Recursive : " << endl;
    
    auto PostOrder = [&](auto &self, Node *root) -> void {
        if (root == NULL) return ;
        self(self, root->left);
        self(self, root->right);
        cout << root->data << ' ';
    };
    
    PostOrder(PostOrder, root);
    cout << '\n';
    
    cout << "PostOrder Iterative :" << endl;
    fill(visited.begin(), visited.end(), false);
    s.push(root);
    visited[root->data] = true;
    while (!s.empty()) {
        Node *head = s.top();
        if (head->left) {
            if (!visited[head->left->data]) {
                s.push(head->left);
                continue;
            }
        }
        if (head->right) {
            if (!visited[head->right->data]) {
                s.push(head->right);
                continue;
            }
        }
        visited[head->data] = true;
        cout << head->data << ' ';
        s.pop();
    }
	return 0;
}