Insertion in a Binary Tree (Level Order)
Insertion In A Binary Tree
Given a tree and a key, add a node in the first available node in the tree. After adding the node, print the level order traversal. In this article, Queue data structure is used to add a node. In this article, we will learn about the process of insertion in a binary tree (Level Order) in C++.
Prerequisite Knowledge:
- A Binary Tree is a data structure with maximum of two children for each parent.
- Level Order Traversal is an example Of Breadth First Search algorithm.
- Level order is a traversal in which each node is visited in the level before we move to a lower level.
- Queues are used to find the level order traversal.
Algorithm:
- Create a queue q.
- If root is NULL, add node and return.
- Else continue until q is not empty.
- If a child does not exists, add the node there.
- Otherwise add the node to the leftmost node.
Code Implementation for Insertion in a Binary Tree in C++
Run
#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode (int x):val (x), left (NULL), right (NULL)
{ }
};
void insert (TreeNode * &root, int val)
{
if (root == NULL)
{
root = new TreeNode (val);
return;
}
if (val < root->val)
{
insert (root->left, val);
}
else
{
insert (root->right, val);
}
}
void inorder_traversal (TreeNode * root)
{
if (root == NULL)
return;
// Visit Left subtree
inorder_traversal (root->left);
// Print the data
cout << root->val << " ";
inorder_traversal (root->right);
// Visit right subtree inorder_traversal (root->right);
}
int main ()
{
TreeNode *root = NULL;
insert (root, 50);
insert (root, 20);
insert (root, 70);
insert (root, 10);
insert (root, 30);
insert (root, 60);
insert (root, 80);
cout << "The binary tree is : ";
inorder_traversal (root);
return 0;
}
Output: The binary tree is : 10 20 30 50 60 70 80
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment