#include <iostream>

// Define the structure of a tree node
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;

TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

// Function to perform DFS in preorder
void DFS(TreeNode* node) {
if (node == nullptr) return;

// Visit the node
std::cout << node->value << " ";

// Traverse the left subtree
DFS(node->left);

// Traverse the right subtree
DFS(node->right);
}

// Function to add a node in the binary search tree
TreeNode* insertBST(TreeNode* root, int value) {
if (root == nullptr) {
return new TreeNode(value);
}

if (value < root->value) {
root->left = insertBST(root->left, value);
} else {
root->right = insertBST(root->right, value);
}

return root;
}

// Main function
int main() {
TreeNode* root = nullptr;

// Example of inserting nodes into the BST
root = insertBST(root, 5);
insertBST(root, 3);
insertBST(root, 7);
insertBST(root, 2);
insertBST(root, 4);
insertBST(root, 6);
insertBST(root, 8);

// Performing DFS on the tree
std::cout << "DFS (Preorder): ";
DFS(root);
std::cout << std::endl;

return 0;
}