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: