Binary Search Tree Insertion

Question | May 3, 2016 | rparekh 

Suppose a binary search tree 'Tree' and its node 'Node' are represented as:

struct Node {
    std::string key;
    Node* left;
    Node* right;
    Node(std::string& k)
       :key(k),left(NULL),right(NULL) {}
};

struct Tree {
    Tree():root(NULL){}
    void Insert(std::string key);
    void Insert(std::string key,Node*& node);
    // .... more methods......
    Node* root;
};

And below is the implementation of Insert functions:

    // called by clients
void Tree::Insert(std::string key) {             
    Insert(key, root);
}

 // called internally 
void Tree::Insert(std::string key,Node*& node) {
    if(!node) 
       node = new Node(key); //Insert new
    else if (key <= node->key) 
       Insert(key,node->left); //go left
    else 
       Insert(key,node->right); //go right
}

Now insert some nodes in an example 'Tree':

    Tree binTree;
    binTree.Insert("E");
    binTree.Insert("F");
    binTree.Insert("G");
    binTree.Insert("A");
    binTree.Insert("B");
    binTree.Insert("A");

What will be the shape of 'binTree' after above insertions? Select the correct answer from one of the options below:

2015 nextptr