Insertion & Deletion in Binary Tree | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

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 the new key as right child. We keep traversing the tree until we find a node whose either left or right is empty.

• C++
  
  
  
  
• Java
  
  
  
  
• Python3
  
  
  
• C#
  
  
  

Output

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

Deletion in a Binary Tree

Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom (i.e. the deleted node is replaced by bottom most and rightmost node). This is different from BST deletion. Here we do not have any order among elements, so we replace with last element.

Examples:

• Delete 10 in below tree
  Output:
  
• Delete 20 in below tree
      Output:
  
      

Algorithm 

1. Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete. 
2. Replace the deepest rightmost node’s data with node to be deleted. 
3. Then delete the deepest rightmost node.
   

• C++
  
  
  
  
  
• Java
  
  
  
  
  
  
• Python3
  
  
  
  
• Javascript
  
  
  
  
  

Output:

• Inorder traversal before deletion: 7 11 12 10 15 9 8
• Inorder traversal after deletion: 7 8 12 10 15 9

Note: We can also replace node’s data that is to be deleted with any node whose left and right child points to NULL but we only use deepest node in order to maintain the Balance of a binary tree.