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);
}
}
}
I am aware of the fact that this is a question posted some time ago, but I still wanted to share my thoughts on it.
What I would do (since this indeed is not very well documented) is use a Breadth-First-Search (using a queue) and insert the child into the first null I encounter. This will ensure that your tree will fill up the levels first before it goes to another level. With the right number of nodes, it will always be complete.
I haven't worked that much with c++, so to be sure it was correct I did it in Java, but you get the idea:
public void insert(Node node) {
if(root == null) {
root = node;
return;
}
/* insert using Breadth-first-search (queue to the rescue!) */
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(true) {
Node n = queue.remove();
if(!n.visited) System.out.println(n.data);
n.visited = true;
if(n.left == null) {
n.left = node;
break;
} else {
queue.offer(n.left);
}
if(n.right == null) {
n.right = node;
break;
} else {
queue.offer(n.right);
}
}
}