Inserting Into A Binary Search Tree

#include<iostream>
#include<vector>
using namespace std;

class Node {

    public:
    int data;
    Node * left;
    Node * right;
    Node(int x) : data(x), left(NULL), right(NULL)
    {}
};

class Tree {

    public:

    vector<int> order;

    /* The in-order traversal of a valid binary search tree is always in increasing order (sorted) */
    void InOrder(Node * node) {

        if (node != NULL) {
            InOrder(node->left);
            cout << node->data << " ";
            order.push_back(node->data);
            InOrder(node->right);
        }
    }

    Node * InsertIntoBST(Node * root, int data) {
        if (root == NULL) {
            root = new Node(data);
        } else if (root->data < data) {
            root->right = InsertIntoBST(root->right, data);
        } else if (root->data > data) {
            root->left = InsertIntoBST(root->left, data);
        }
        return root;
    }
};

int main() {

    /*   6 
        / \
       4   9  */

    Node * root1 = new Node(6);
    root1->left = new Node(4);
    root1->right = new Node(9);

    Tree t;
    cout << "Before Inserting 5 : ";
    t.InOrder(root1);
    root1 = t.InsertIntoBST(root1, 5);
    cout << "\nAfter Inserting 5 : ";
    t.InOrder(root1);

    /*   5
        / \
       1   7  
            \
             8  */
    Node * root2 = new Node(5);
    root2->left = new Node(1);
    root2->right = new Node(7);
    root2->right->right = new Node(8);

    cout << "\n\nBefore Inserting 6 : ";
    t.InOrder(root2);
    root1 = t.InsertIntoBST(root2, 6);
    cout << "\nAfter Inserting 6 : ";
    t.InOrder(root2);

    /*   2 
        / 
       1   */
    Node * root3 = new Node(2);
    root3->left = new Node(1);

    cout << "\n\nBefore Inserting 4 : ";
    t.InOrder(root3);
    root1 = t.InsertIntoBST(root3, 4);
    cout << "\nAfter Inserting 4 : ";
    t.InOrder(root3);

    return 0;
}

Before Inserting 5 : 4 6 9 
After Inserting 5 : 4 5 6 9 

Before Inserting 6 : 1 5 7 8 
After Inserting 6 : 1 5 6 7 8 

Before Inserting 4 : 1 2 
After Inserting 4 : 1 2 4