#include <iostream>
#include <cstddef>
#include <deque>

class Node {
    public:
        int data;
        Node *left;
        Node *right;
        Node(int d) {
            data = d;
            left = NULL;
            right = NULL;
        }
};

class Solution {
    public:
  		Node* insert(Node* root, int data) {
            if(root == NULL) {
                return new Node(data);
            } else {
                Node* cur;
                if(data <= root->data) {
                    cur = insert(root->left, data);
                    root->left = cur;
                } else {
                    cur = insert(root->right, data);
                    root->right = cur;
                }

               return root;
           }
        }

/* you only have to complete the function given below.
Node is defined as

class Node {
    public:
        int data;
        Node *left;
        Node *right;
        Node(int d) {
            data = d;
            left = NULL;
            right = NULL;
        }
};

*/

//    void preOrder(Node *root) {
//        /* #include <deque> */
//        std::deque<Node*> q {root};
//
//        while (!q.empty()) {
//            auto elem = q.back();
//
//            q.pop_back();
//
//            while (elem != nullptr) {
//                if (elem->right != nullptr) {
//                    q.push_back(elem->right);
//                }
//
//                std::cout << elem->data << " ";
//
//                elem = elem->left;
//            }
//        }
//    }

    void printLeft(Node *left, Node *right) {

        while (left != nullptr) {
            std::cout << " " << left->data;

            if (left->right != nullptr) {
                printLeft(left->left, left->right);
                break;
            }

            left = left->left;
        }

        if (right != nullptr) {
            std::cout << " " << right->data;

            printLeft(right->left, right->right);
        }
    }

    void preOrder(Node *root) {
        if (root == nullptr) {
            return;
        }

        std::cout << root->data;

        printLeft(root->left, root->right);
    }

}; //End of Solution

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}