title: C++ BST tree insert a string
body: <p>I am trying to create a BST whose data is a string.. however, it doesn't seem to like the string value..if i change the data type to int, the code works.. i am not sure why..can someone help?
  here is the code</p>
  
  <pre><code>// BST.cpp : Defines the entry point for the console application.
  //
  
  #include "stdafx.h"
  #include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;string&gt;
  #include&lt;iostream&gt;
  
  using namespace std;
  
  // An AVL tree node
  struct Node
  {
      string key;
      struct Node *left;
      struct Node *right;
      int height;
      int counter;
  };
  
  // A utility function to get maximum of two integers
  int max(int a, int b);
  
  // A utility function to get height of the tree
  int height(struct Node *N)
  {
      if (N == NULL)
          return 0;
      return N-&gt;height;
  }
  
  // A utility function to get maximum of two integers
  int max(int a, int b)
  {
      return (a &gt; b) ? a : b;
  }
  
  /* Helper function that allocates a new node with the given key and
  NULL left and right pointers. */
  struct Node* newNode(const string&amp; key)
  {
      struct Node* node = (struct Node*)
          malloc(sizeof(struct Node));
      node-&gt;key = key;
      node-&gt;left = nullptr;
      node-&gt;right = nullptr;
      node-&gt;counter = 0;
      node-&gt;height = 1; // new node is initially added at leaf
      return(node);
  }
  
  // A utility function to right rotate subtree rooted with y
  // See the diagram given above.
  struct Node *rightRotate(struct Node *y)
  {
      struct Node *x = y-&gt;left;
      struct Node *T2 = x-&gt;right;
  
      // Perform rotation
      x-&gt;right = y;
      y-&gt;left = T2;
  
      // Update heights
      y-&gt;height = max(height(y-&gt;left), height(y-&gt;right)) + 1;
      x-&gt;height = max(height(x-&gt;left), height(x-&gt;right)) + 1;
  
      // Return new root
      return x;
  }
  
  // A utility function to left rotate subtree rooted with x
  // See the diagram given above.
  struct Node *leftRotate(struct Node *x)
  {
      struct Node *y = x-&gt;right;
      struct Node *T2 = y-&gt;left;
  
      // Perform rotation
      y-&gt;left = x;
      x-&gt;right = T2;
  
      // Update heights
      x-&gt;height = max(height(x-&gt;left), height(x-&gt;right)) + 1;
      y-&gt;height = max(height(y-&gt;left), height(y-&gt;right)) + 1;
  
      // Return new root
      return y;
  }
  
  // Get Balance factor of node N
  int getBalance(struct Node *N)
  {
      if (N == NULL)
          return 0;
      return height(N-&gt;left) - height(N-&gt;right);
  }
  
  // Recursive function to insert key in subtree rooted
  // with node and returns new root of subtree.
  struct Node* insert(struct Node* node, string key)
  
  
  {
      /* 1. Perform the normal BST insertion */
      if (node == NULL)
          return(newNode(key));
  
      if (key &lt; node-&gt;key)
          node-&gt;left = insert(node-&gt;left, key);
      else if (key &gt; node-&gt;key)
          node-&gt;right = insert(node-&gt;right, key);
      else // Equal keys are not allowed in BST
      {
          node-&gt;counter++;
          return node;
      }
      /* 2. Update height of this ancestor node */
      node-&gt;height = 1 + max(height(node-&gt;left),
          height(node-&gt;right));
  
      /* 3. Get the balance factor of this ancestor
      node to check whether this node became
      unbalanced */
      int balance = getBalance(node);
  
      // If this node becomes unbalanced, then
      // there are 4 cases
  
      // Left Left Case
      if (balance &gt; 1 &amp;&amp; key &lt; node-&gt;left-&gt;key)
          return rightRotate(node);
  
      // Right Right Case
      if (balance &lt; -1 &amp;&amp; key &gt; node-&gt;right-&gt;key)
          return leftRotate(node);
  
      // Left Right Case
      if (balance &gt; 1 &amp;&amp; key &gt; node-&gt;left-&gt;key)
      {
          node-&gt;left = leftRotate(node-&gt;left);
          return rightRotate(node);
      }
  
      // Right Left Case
      if (balance &lt; -1 &amp;&amp; key &lt; node-&gt;right-&gt;key)
      {
          node-&gt;right = rightRotate(node-&gt;right);
          return leftRotate(node);
      }
  
      /* return the (unchanged) node pointer */
      return node;
  }
  
  // A utility function to print preorder traversal
  // of the tree.
  // The function also prints height of every node
  void preOrder(struct Node *root)
  {
      if (root)
      {
          cout &lt;&lt; root-&gt;key &lt;&lt; endl;;
          preOrder(root-&gt;left);
          preOrder(root-&gt;right);
      }
  }
  
  /* Drier program to test above function*/
  int main()
  {
      struct Node *root = nullptr;
  
      /* Constructing tree given in the above figure */
  
      root = insert(root, "a");
      root = insert(root, "bc");
      root = insert(root, "DE");
      root = insert(root, "op");
      root = insert(root, "lo");
      root = insert(root, "mp");
  
      /*root = insert(root, 10);
      root = insert(root, 20);
      root = insert(root, 30);
      root = insert(root, 40);
      root = insert(root, 50);
      root = insert(root, 25);*/
  
      printf("Preorder traversal of the constructed AVL"
          " tree is \n");
      preOrder(root);
  
      return 0;
  }
  </code></pre>