Pre-Order Traversal of a Tree

Given an array of integers. Create a Binary Search Tree from these numbers. If the inserted value equals the current node, insert it to the right subtree.

Write method PreOrder that makes Pre-Order traversal of a tree. In this traversal method the root node is visited first, then the left subtree and finally the right subtree.

Write the code according to the next interface:

// C++
class TreeNode
{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Tree 
{
public:
    TreeNode *head;
    Tree() : head(NULL) {};
    void Insert(int val); // Insert number val to Binary Search Tree
    void PreOrder(void); // Print the vertices of a tree according to pre-order traversal
};

You can create (use) additional methods if needed.