Binary tree Insert?

[tay1392]

Hello everyone. I recently finished implementing a Binary search tree for a project I was working on. It went well and I learned a lot. However, now I need to implement a regular Binary Tree... which for some reason has me stumped.

I'm looking for a way to do my InsertNode function..

normally in a BST you just check if data < root then insert left and vice versa. However, In a normal Binary tree, it is just filled from left to right, one level at a time..

could anyone help me implement a function that just adds a new Node to the Binary tree from left to right in no specific order?

Here's my Insert for a BST:

void Insert(Node *& root, int data)
{
  if(root == nullptr)
  {
    Node * nn = new Node;
    root = nn;
  }
  else
  {
    if(data < root->data)
    { 
      Insert(root->left, data);
    }
    else
    {
      Insert(root->right, data);
    }
  }
}

Thanks any help would be appreciated!

[tay1392]

Anyone??

[Duthomhas]

void Insert(Node *& root, int data)
{
  if(root == nullptr)
  {
    Node * nn = new Node;
    root = nn;
    nn->data = data;  // Don't forget me!
  }
  else
  {
    if(data < root->data)
    { 
      Insert(root->left, data);
    }
    else
    {
      Insert(root->right, data);
    }
  }
}

Hope this helps.

[tay1392]

Thanks for the response Duoas but it's not quite what I was looking for, see a Binary Tree is different from a binary SEARCH tree, which is implemented above. I need help making a Binary tree insert. Just a simple, left to right insert. Thanks again, though.

[ne555]

std::vector<int> nodes

insert(int data){
   nodes.push_back(data);
}

You can obtain the children of the K node by doing 2*K+1 and 2*K+2

[Duthomhas]

I know what they are. And to be pedantic, a BST is a type of binary tree with a specific constraint on it.

Besides the code correction for the BST insert, what exactly is the problem you have?

ne555's solution is not modeled the same way your tree is, but it is how most straight-up binary trees are modeled. If you want to add nodes the same way (top to bottom, left to right) using your linked node model, then you will need some careful logic to locate the proper node. Frankly, it is more trouble than it is worth that way.