title: Why does my AVL-Insertion return segmentation fault after a large input?
body: <p>I am implementing the avl tree structure. When i run the insertion operation, I see a strange thing happen: if the input is small enough, i.e. 10 or 20, then the insertion runs fine. Once I try to insert 100 elements then everything goes to a seg fault and no matter what I do, it does not run correctly afterwards.</p>
  
  <p>I have tried lots of advice from this site and my own debugging/tracing on paper, can't seem to catch the error.</p>
  
  <p>This is my insertion operation:</p>
  
  <pre><code>Node *AVLTree::insert(Node *node, int key)
  {
      /*
      insert a node into a binary tree.
      */
      if (node == NIL)
      {
          return (newNode(key)); // O(1)
      }
      if (key &lt; node-&gt;val)
      {
          node-&gt;left = this-&gt;insert(node-&gt;left, key); // T(n/2)
          node-&gt;left-&gt;p = node;
      }
      else if (key &gt; node-&gt;val)
      {
          node-&gt;right = this-&gt;insert(node-&gt;right, key); // T(n/2)
          node-&gt;right-&gt;p = node;
      }
      else
      {
          return node;
      }
      node-&gt;height = 1 + fmax(height(node-&gt;left), height(node-&gt;right)); // O(i log i) where i is the number of nodes in the current subtree
      int balance = this-&gt;get_balance(node);                            // O(1)
      if (balance &gt; 1 &amp;&amp; node-&gt;left != NIL &amp;&amp; key &lt; node-&gt;left-&gt;val)
      {
          return this-&gt;right_rotate(node); // O(1)
      }
      if (balance &gt; 1 &amp;&amp; node-&gt;left != NIL &amp;&amp; key &gt; node-&gt;left-&gt;val)
      {
          node-&gt;left = this-&gt;left_rotate(node-&gt;left);
          return this-&gt;right_rotate(node); // O(1)
      }
      if (balance &lt; -1 &amp;&amp; node-&gt;right != NIL &amp;&amp; key &gt; node-&gt;right-&gt;val)
      {
          return this-&gt;left_rotate(node); // O(1)
      }
      if (balance &lt; -1 &amp;&amp; node-&gt;right != NIL &amp;&amp; key &lt; node-&gt;right-&gt;val)
      {
          node-&gt;right = this-&gt;right_rotate(node-&gt;right);
          return this-&gt;left_rotate(node); // O(1)
      }
      return node;
  }
  </code></pre>
  
  <p>These are left and right rotations</p>
  
  <pre><code>Node *AVLTree::left_rotate(Node *x)
  {
      Node *y = x-&gt;right;
      x-&gt;right = y-&gt;left;
      if (y-&gt;left != NIL)
      {
          y-&gt;left-&gt;p = x;
      }
      y-&gt;p = x-&gt;p;
      if (x-&gt;p == NIL)
      {
          this-&gt;root = y;
      }
      else if (x == x-&gt;p-&gt;left)
      {
          x-&gt;p-&gt;left = y;
      }
      else
      {
          x-&gt;p-&gt;right = y;
      }
      y-&gt;left = x;
      x-&gt;p = y;
      x-&gt;height = 1 + fmax(height(x-&gt;left), height(x-&gt;right));
      y-&gt;height = 1 + fmax(height(y-&gt;left), height(y-&gt;right));
      return y;
  }
  
  Node *AVLTree::right_rotate(Node *y)
  {
      Node *x = y-&gt;left;
      y-&gt;left = x-&gt;right;
      if (x-&gt;right != NIL)
      {
          x-&gt;right-&gt;p = y;
      }
      x-&gt;p = y-&gt;p;
      if (y-&gt;p == NIL)
      {
          this-&gt;root = x;
      }
      else if (y == y-&gt;p-&gt;left)
      {
          y-&gt;p-&gt;left = x;
      }
      else
      {
          y-&gt;p-&gt;right = x;
      }
      x-&gt;right = y;
      y-&gt;p = x;
      x-&gt;height = 1 + fmax(height(x-&gt;left), height(x-&gt;right));
      y-&gt;height = 1 + fmax(height(y-&gt;left), height(y-&gt;right));
      return x;
  }
  </code></pre>
  
  <p>my main code is below</p>
  
  <pre><code>int main(int argc, char const *argv[])
  {
      vector&lt;int&gt; A = create_random_data(atoi(argv[1]), atoi(argv[2]), atoi(argv[3])); // creates a vector of size argv[1] with random ints between argv[2] and argv[3]
      Node *root = NIL;
  
      AVLTree tree = AVLTree(root);
      display(A); // displays input array
      for (size_t i = 0; i &lt; A.size(); i++)
      {
          tree.root = tree.insert(tree.root, A[i]);
      }
  }
  </code></pre>
  
  <p>Error occurs in the insertion loop and I tried to trace where exactly but it's hard to tell. Thanks for any recommendation/advice!</p>