# insertion in binary tree

use level order traversal of the given tree using a queue. If we find a node whose left child is empty, we make new key as the left child of the node. Else if we find a node whose right child is empty, we make new key as the right child of that node. We keep traversing the tree until we find a node whose either left or right child is empty.

c++:

```
void insert(struct Node* temp, int key)
{
queue<struct Node*> q;
q.push(temp);
// Do level order traversal until we find
// an empty place.
while (!q.empty()) {
struct Node* temp = q.front();
q.pop();
if (!temp->left) {
temp->left = newNode(key);
break;
} else
q.push(temp->left);
if (!temp->right) {
temp->right = newNode(key);
break;
} else
q.push(temp->right);
}
}
```

java:

```
static void insert(Node temp, int key)
{
Queue<Node> q = new LinkedList<Node>();
q.add(temp);
// Do level order traversal until we find
// an empty place.
while (!q.isEmpty()) {
temp = q.peek();
q.remove();
if (temp.left == null) {
temp.left = new Node(key);
break;
} else
q.add(temp.left);
if (temp.right == null) {
temp.right = new Node(key);
break;
} else
q.add(temp.right);
}
}
```