# Insertion in a Binary Tree in level order

Given a binary tree and a key, insert the key into the binary tree at first position available in level order.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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

## C++

 `// C++ program to insert element in binary tree ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree node has key, pointer to left child ` `and a pointer to right child */` `struct` `Node { ` `    ``int` `key; ` `    ``struct` `Node* left, *right; ` `}; ` ` `  `/* function to create a new node of tree and r ` `   ``eturns pointer */` `struct` `Node* newNode(``int` `key) ` `{ ` `    ``struct` `Node* temp = ``new` `Node; ` `    ``temp->key = key; ` `    ``temp->left = temp->right = NULL; ` `    ``return` `temp; ` `}; ` ` `  `/* Inorder traversal of a binary tree*/` `void` `inorder(``struct` `Node* temp) ` `{ ` `    ``if` `(!temp) ` `        ``return``; ` ` `  `    ``inorder(temp->left); ` `    ``cout << temp->key << ``" "``; ` `    ``inorder(temp->right); ` `} ` ` `  `/*function to insert element in binary tree */` `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); ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``struct` `Node* root = newNode(10); ` `    ``root->left = newNode(11); ` `    ``root->left->left = newNode(7); ` `    ``root->right = newNode(9); ` `    ``root->right->left = newNode(15); ` `    ``root->right->right = newNode(8); ` ` `  `    ``cout << ``"Inorder traversal before insertion:"``; ` `    ``inorder(root); ` ` `  `    ``int` `key = 12; ` `    ``insert(root, key); ` ` `  `    ``cout << endl; ` `    ``cout << ``"Inorder traversal after insertion:"``; ` `    ``inorder(root); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to insert element in binary tree ` `import` `java.util.LinkedList; ` `import` `java.util.Queue; ` `public` `class` `GFG { ` `      `  `    ``/* A binary tree node has key, pointer to  ` `    ``left child and a pointer to right child */` `    ``static` `class` `Node { ` `        ``int` `key; ` `        ``Node left, right; ` `         `  `        ``// constructor ` `        ``Node(``int` `key){ ` `            ``this``.key = key; ` `            ``left = ``null``; ` `            ``right = ``null``; ` `        ``} ` `    ``} ` `    ``static` `Node root; ` `    ``static` `Node temp = root; ` `     `  `    ``/* Inorder traversal of a binary tree*/` `    ``static` `void` `inorder(Node temp) ` `    ``{ ` `        ``if` `(temp == ``null``) ` `            ``return``; ` `      `  `        ``inorder(temp.left); ` `        ``System.out.print(temp.key+``" "``); ` `        ``inorder(temp.right); ` `    ``} ` `      `  `    ``/*function to insert element in binary tree */` `    ``static` `void` `insert(Node temp, ``int` `key) ` `    ``{ ` `        ``Queue q = ``new` `LinkedList(); ` `        ``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); ` `        ``} ` `    ``} ` `      `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``root = ``new` `Node(``10``); ` `        ``root.left = ``new` `Node(``11``); ` `        ``root.left.left = ``new` `Node(``7``); ` `        ``root.right = ``new` `Node(``9``); ` `        ``root.right.left = ``new` `Node(``15``); ` `        ``root.right.right = ``new` `Node(``8``); ` `      `  `        ``System.out.print( ``"Inorder traversal before insertion:"``); ` `        ``inorder(root); ` `      `  `        ``int` `key = ``12``; ` `        ``insert(root, key); ` `      `  `        ``System.out.print(````" Inorder traversal after insertion:"````); ` `        ``inorder(root); ` `    ``} ` `} ` `// This code is contributed by Sumit Ghosh `

## Python3

 `# Python program to insert element in binary tree  ` `class` `newNode():  ` ` `  `    ``def` `__init__(``self``, data):  ` `        ``self``.key ``=` `data ` `        ``self``.left ``=` `None` `        ``self``.right ``=` `None` `         `  `""" Inorder traversal of a binary tree"""` `def` `inorder(temp): ` ` `  `    ``if` `(``not` `temp): ` `        ``return` ` `  `    ``inorder(temp.left)  ` `    ``print``(temp.key,end ``=` `" "``) ` `    ``inorder(temp.right)  ` ` `  ` `  `"""function to insert element in binary tree """` `def` `insert(temp,key): ` ` `  `    ``q ``=` `[]  ` `    ``q.append(temp)  ` ` `  `    ``# Do level order traversal until we find  ` `    ``# an empty place.  ` `    ``while` `(``len``(q)):  ` `        ``temp ``=` `q[``0``]  ` `        ``q.pop(``0``)  ` ` `  `        ``if` `(``not` `temp.left): ` `            ``temp.left ``=` `newNode(key)  ` `            ``break` `        ``else``: ` `            ``q.append(temp.left)  ` ` `  `        ``if` `(``not` `temp.right): ` `            ``temp.right ``=` `newNode(key)  ` `            ``break` `        ``else``: ` `            ``q.append(temp.right)  ` `     `  `# Driver code  ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``root ``=` `newNode(``10``)  ` `    ``root.left ``=` `newNode(``11``)  ` `    ``root.left.left ``=` `newNode(``7``)  ` `    ``root.right ``=` `newNode(``9``)  ` `    ``root.right.left ``=` `newNode(``15``)  ` `    ``root.right.right ``=` `newNode(``8``)  ` ` `  `    ``print``(``"Inorder traversal before insertion:"``, end ``=` `" "``) ` `    ``inorder(root)  ` ` `  `    ``key ``=` `12` `    ``insert(root, key)  ` ` `  `    ``print``()  ` `    ``print``(``"Inorder traversal after insertion:"``, end ``=` `" "``) ` `    ``inorder(root) ` ` `  `# This code is contributed by SHUBHAMSINGH10 `

Output:

```Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8
```

Tree Tree