C++ iterative insert into binary search tree BST

Question

My function works as long as item is smaller and therefore inserted to the left, but when it should go right, nothing seems to happen. It doesn't crash or anything, it just doesn't do the insert.

I don't get how this could happen because the only different in the code in either case is the words left or right (as far as I can see). Anything obvious to someone more experienced?

template <typename T>
void BST<T>::insertHelper(BST<T>::BinNodePtr &subRoot, const T& item)
{
  BinNode *newNode;
  BinNode *parent;
  BinNode *child;

  newNode = new BinNode;
  newNode->data = item;
  // newNode->left = NULL;
  // newNode->right = NULL;

  parent = subRoot;
  child = subRoot;

  if (!subRoot){
    subRoot = newNode;
  } else {

    if (item < child->data){
      child = child->left;
    } else if (item > child->data){
      child = child->right;
    }
    while (child){
      parent = child;
      if (item < child->data){
        child = child->left;
      } else if (item > child->data){
        child = child->right;
      }
    }
    child = newNode;
    if (child->data < parent->data)
      parent->left = child;
    else if (child->data < parent->data)
      parent->right = child;
  }
}

just put some printf() debug outputs here and there to follow how the decisions at every if are made, and you will see the wrong decision in the last if clause. — Pavel
– Pavel, Commented May 13, 2014 at 22:49
if item == subRoot->data the while go in a endless loop. What is T in your test case? T have a comparison operator override? — ilmale
– ilmale, Commented May 13, 2014 at 22:50

Siddhartha · Accepted Answer · 2014-05-13 22:48:00Z

3

Your last 'if' and 'else if' have the same condition. The second one should be '>'

answered May 13, 2014 at 22:48

Siddhartha

4,4748 gold badges46 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

C++ iterative insert into binary search tree BST

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related