TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Program to Construct a Binary Search Tree and Perform Deletion and Inorder Traversal

Program to Construct a Binary Search Tree and Perform Deletion and Inorder Traversal on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

<< Back to PROGRAM

Q. Program to construct a Binary Search Tree and perform deletion and inorder traversal.

Explanation

In this program, we need to create a binary search tree, delete a node from the tree, and display the nodes of the tree by traversing the tree using in-order traversal. In in-order traversal, for a given node, first, we traverse the left child then root then right child (Left -> Root -> Right).

Program to construct a Binary Search Tree and perform deletion and inorder traversal

In Binary Search Tree, all nodes which are present to the left of root will be less than root node and nodes which are present to the right will be greater than the root node.

Insertion:

  1. If the value of the new node is less than the root node then, it will be inserted to the left subtree.
  2. If the value of the new node is greater than root node then, it will be inserted to the right subtree.

Deletion:

  1. If the node to be deleted is a leaf node then, parent of that node will point to null. For eg. If we delete 90, then parent node 70 will point to null.
  2. If the node to be deleted has one child node, then child node will become a child node of the parent node. For eg. If we delete 30, then node 10 which was left child of 30 will become left child of 50.
  3. If the node to be deleted has two children then, we find the node(minNode) with minimum value from the right subtree of that current node. The current node will be replaced by its successor(minNode).

Algorithm

  1. Define Node class which has three attributes namely: data, left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to the data attribute of the node and both left and right will be set to null.
  3. Define another class which has an attribute root.
    1. Root represents the root node of the tree and initializes it to null.
  4. insert() will insert the new value into a binary search tree:
    1. It checks whether root is null, which means tree is empty. New node will become root node of tree.
    2. If tree is not empty, it will compare value of new node with root node. If value of new node is greater than root, new node will be inserted to right subtree. Else, it will be inserted in left subtree.
  5. deleteNode() will delete a particular node from the tree:
    1. If value of node to be deleted is less than root node, search node in left subtree. Else, search in right subtree.
    2. If node is found and it has no children, then set the node to null.
    3. If node has one child then, child node will take position of node.
    4. If node has two children then, find a minimum value node from its right subtree. This minimum value node will replace the current node.

Solution

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class BinarySearchTree:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        
    #insert() will add new node to the binary search tree
    def insert(self, data):
        #Create a new node
        newNode = Node(data);
        
        #Check whether tree is empty
        if(self.root == None):
            self.root = newNode;
            return;
        else:
            #current node point to root of the tree
            current = self.root;
            
            while(True):
                #parent keep track of the parent node of current node.
                parent = current;
                
                #If data is less than current's data, node will be inserted to the left of tree
                if(data < current.data):
                    current = current.left;
                    if(current == None):
                        parent.left = newNode;
                        return;
                        
                #If data is greater than current's data, node will be inserted to the right of tree
                else:
                    current = current.right;
                    if(current == None):
                        parent.right = newNode;
                        return;
                        
    #minNode() will find out the minimum node
    def minNode(self, root):
        if(root.left != None):
            return self.minNode(root.left);
        else:
            return root;
            
    #deleteNode() will delete the given node from the binary search tree
    def deleteNode(self, node, value):
        if(node == None):
            return None;
        else:
            #value is less than node's data then, search the value in left subtree
            if(value < node.data):
                node.left = self.deleteNode(node.left, value);
            
            #value is greater than node's data then, search the value in right subtree
            elif(value > node.data):
                node.right = self.deleteNode(node.right, value);
                
            #If value is equal to node's data that is, we have found the node to be deleted
            else:
                #If node to be deleted has no child then, set the node to None
                if(node.left == None and node.right == None):
                    node = None;
                    
                #If node to be deleted has only one right child
                elif(node.left == None):
                    node = node.right;
                
                #If node to be deleted has only one left child
                elif(node.right == None):
                    node = node.left;
                    
                #If node to be deleted has two children node
                else:
                    #then find the minimum node from right subtree
                    temp = self.minNode(node.right);
                    #Exchange the data between node and temp
                    node.data = temp.data;
                    #Delete the node duplicate node from right subtree
                    node.right = self.deleteNode(node.right, temp.data);
        return node;
                
    #inorder() will perform inorder traversal on binary search tree
    def inorderTraversal(self, node):
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty");
            return;
        else:
            if(node.left != None):
                self.inorderTraversal(node.left);
            print(node.data, end=" ");
            if(node.right != None):
                self.inorderTraversal(node.right);
                
bt = BinarySearchTree();
#Add nodes to the binary tree
bt.insert(50);
bt.insert(30);
bt.insert(70);
bt.insert(60);
bt.insert(10);
bt.insert(90);
 
print("Binary search tree after insertion:");
#Displays the binary tree
bt.inorderTraversal(bt.root);
 
#Deletes node 90 which has no child
deletedNode = bt.deleteNode(bt.root, 90);
print("\nBinary search tree after deleting node 90:");
bt.inorderTraversal(bt.root);
 
#Deletes node 30 which has one child
deletedNode = bt.deleteNode(bt.root, 30);
print("\nBinary search tree after deleting node 30:");
bt.inorderTraversal(bt.root);
 
#Deletes node 50 which has two children
deletedNode = bt.deleteNode(bt.root, 50);
print("\nBinary search tree after deleting node 50:");
bt.inorderTraversal(bt.root);

Output:

Binary search tree after insertion:
10 30 50 60 70 90 
Binary search tree after deleting node 90:
10 30 50 60 70 
Binary search tree after deleting node 30:
10 50 60 70 
Binary search tree after deleting node 50:
10 60 70

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root= NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data= data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//insert() will add new node to the binary search tree
void insert(int data) {
    //Create a new node
    struct node *newNode = createNode(data);
    
    //Check whether tree is empty
    if(root == NULL){
        root = newNode;
        return;
      }
    else {
        //current node point to root of the tree
        struct node *current = root, *parent = NULL;
        
        while(true) {
            //parent keep track of the parent node of current node.
            parent = current;
 
            //If data is less than current's data, node will be inserted to the left of tree
            if(data < current->data) {
                current = current->left;
                if(current == NULL) {
                    parent->left = newNode;
                    return;
                }
            }
            //If data is greater than current's data, node will be inserted to the right of tree
            else {
                current = current->right;
                if(current == NULL) {
                    parent->right = newNode;
                    return;
                }
            }
        }
    }
}
 
//minNode() will find out the minimum node
struct node* minNode(struct node *root) {
    if (root->left != NULL)
        return minNode(root->left);
    else 
        return root;
} 
 
//deleteNode() will delete the given node from the binary search tree
struct node* deleteNode(struct node *node, int value) {
    if(node == NULL){
          return NULL;
     }
    else {
        //value is less than node's data then, search the value in left subtree
        if(value < node->data)
            node->left = deleteNode(node->left, value);
        
        //value is greater than node's data then, search the value in right subtree
        else if(value > node->data)
            node->right = deleteNode(node->right, value);
        
        //If value is equal to node's data that is, we have found the node to be deleted
        else {
            //If node to be deleted has no child then, set the node to NULL
            if(node->left == NULL && node->right == NULL)
                node = NULL;
            
            //If node to be deleted has only one right child
            else if(node->left == NULL) {
                node = node->right;
            }
            
            //If node to be deleted has only one left child
            else if(node->right == NULL) {
                node = node->left;
            }
            
            //If node to be deleted has two children node
            else {
                //then find the minimum node from right subtree
                struct node *temp = minNode(node->right);
                //Exchange the data between node and temp
                node->data = temp->data;
                //Delete the node duplicate node from right subtree
                node->right = deleteNode(node->right, temp->data);
            }
        }
        return node;
    }
}
 
//inorder() will perform inorder traversal on binary search tree
void inorderTraversal(struct node *node) {
      
    //Check whether tree is empty
    if(root == NULL){
        printf("Tree is empty\n");
          return;
     }
    else {
          
        if(node->left!= NULL)
            inorderTraversal(node->left);
        printf("%d ", node->data);
        if(node->right!= NULL)
          inorderTraversal(node->right);
          
    }      
}
      
int main()
{
    //Add nodes to the binary tree
    insert(50);
    insert(30);
    insert(70);
    insert(60);
    insert(10);
    insert(90);
    
    printf("Binary search tree after insertion: \n");
    //Displays the binary tree
    inorderTraversal(root);
    
    struct node *deletedNode = NULL;
    //Deletes node 90 which has no child
    deletedNode = deleteNode(root, 90);
    printf("\nBinary search tree after deleting node 90: \n");
    inorderTraversal(root);
    
    //Deletes node 30 which has one child
    deletedNode = deleteNode(root, 30);
    printf("\nBinary search tree after deleting node 30: \n");
    inorderTraversal(root);
    
    //Deletes node 50 which has two children
    deletedNode = deleteNode(root, 50);
    printf("\nBinary search tree after deleting node 50: \n");
    inorderTraversal(root);
 
    return 0;
}

Output:

Binary search tree after insertion:
10 30 50 60 70 90 
Binary search tree after deleting node 90:
10 30 50 60 70 
Binary search tree after deleting node 30:
10 50 60 70 
Binary search tree after deleting node 50:
10 60 70

JAVA

public class BinarySearchTree {
    
    //Represent a node of binary tree
    public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
        }
      }
      
      //Represent the root of binary tree
      public Node root;
      
      public BinarySearchTree(){
          root = null;
      }
      
      //insert() will add new node to the binary search tree
      public void insert(int data) {
          //Create a new node
          Node newNode = new Node(data);
          
          //Check whether tree is empty
          if(root == null){
              root = newNode;
              return;
            }
          else {
              //current node point to root of the tree
              Node current = root, parent = null;
              
              while(true) {
                  //parent keep track of the parent node of current node.
                  parent = current;
 
                  //If data is less than current's data, node will be inserted to the left of tree
                  if(data < current.data) {
                      current = current.left;
                      if(current == null) {
                          parent.left = newNode;
                          return;
                      }
                  }
                  //If data is greater than current's data, node will be inserted to the right of tree
                  else {
                      current = current.right;
                      if(current == null) {
                          parent.right = newNode;
                          return;
                      }
                  }
              }
          }
      }
      
      //minNode() will find out the minimum node
      public Node minNode(Node root) {
          if (root.left != null)
              return minNode(root.left);
          else 
              return root;
      } 
      
      //deleteNode() will delete the given node from the binary search tree
      public Node deleteNode(Node node, int value) {
          if(node == null){
              return null;
           }
          else {
              //value is less than node's data then, search the value in left subtree
              if(value < node.data)
                  node.left = deleteNode(node.left, value);
              
              //value is greater than node's data then, search the value in right subtree
              else if(value > node.data)
                  node.right = deleteNode(node.right, value);
              
              //If value is equal to node's data that is, we have found the node to be deleted
              else {
                  //If node to be deleted has no child then, set the node to null
                  if(node.left == null && node.right == null)
                      node = null;
                  
                  //If node to be deleted has only one right child
                  else if(node.left == null) {
                      node = node.right;
                  }
                  
                  //If node to be deleted has only one left child
                  else if(node.right == null) {
                      node = node.left;
                  }
                  
                  //If node to be deleted has two children node
                  else {
                      //then find the minimum node from right subtree
                      Node temp = minNode(node.right);
                      //Exchange the data between node and temp
                      node.data = temp.data;
                      //Delete the node duplicate node from right subtree
                      node.right = deleteNode(node.right, temp.data);
                  }
              }
              return node;
          }
      }
      
      //inorder() will perform inorder traversal on binary search tree
      public void inorderTraversal(Node node) {
          
          //Check whether tree is empty
          if(root == null){
              System.out.println("Tree is empty");
              return;
           }
          else {
              
              if(node.left!= null)
                  inorderTraversal(node.left);
              System.out.print(node.data + " ");
              if(node.right!= null)
                  inorderTraversal(node.right);
              
          }      
      }
      
      public static void main(String[] args) {
          
          BinarySearchTree bt = new BinarySearchTree();
          //Add nodes to the binary tree
          bt.insert(50);
          bt.insert(30);
          bt.insert(70);
          bt.insert(60);
          bt.insert(10);
          bt.insert(90);
          
          System.out.println("Binary search tree after insertion:");
          //Displays the binary tree
          bt.inorderTraversal(bt.root);
          
          Node deletedNode = null;
          //Deletes node 90 which has no child
          deletedNode = bt.deleteNode(bt.root, 90);
          System.out.println("\nBinary search tree after deleting node 90:");
          bt.inorderTraversal(bt.root);
          
          //Deletes node 30 which has one child
          deletedNode = bt.deleteNode(bt.root, 30);
          System.out.println("\nBinary search tree after deleting node 30:");
          bt.inorderTraversal(bt.root);
          
          //Deletes node 50 which has two children
          deletedNode = bt.deleteNode(bt.root, 50);
          System.out.println("\nBinary search tree after deleting node 50:");
          bt.inorderTraversal(bt.root);
      }
}

Output:

Binary search tree after insertion:
10 30 50 60 70 90 
Binary search tree after deleting node 90:
10 30 50 60 70 
Binary search tree after deleting node 30:
10 50 60 70 
Binary search tree after deleting node 50:
10 60 70

C#

 using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class BinarySearchTree<T> where T : IComparable<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            public BinarySearchTree(){
                root = null;
            }
            
        //insert() will add new node to the binary search tree
        public void insert(T data) {
          //Create a new node
          Node<T> newNode = new Node<T>(data);
          
          //Check whether tree is empty
          if(root == null){
              root = newNode;
              return;
            }
          else {
              //current node point to root of the tree
              Node<T> current = root, parent = null;
              
              while(true) {
                  //parent keep track of the parent node of current node.
                  parent = current;
 
                  //If data is less than current's data, node will be inserted to the left of tree
                  if(data.CompareTo(current.data) < 0) {
                      current = current.left;
                      if(current == null) {
                          parent.left = newNode;
                          return;
                      }
                  }
                  //If data is greater than current's data, node will be inserted to the right of tree
                  else {
                      current = current.right;
                      if(current == null) {
                          parent.right = newNode;
                          return;
                      }
                  }
              }
          }
        }
      
        //minNode() will find out the minimum node
        public Node<T> minNode(Node<T> root) {
          if (root.left != null)
              return minNode(root.left);
          else 
              return root;
        } 
        
        //deleteNode() will delete the given node from the binary search tree
        public Node<T> deleteNode(Node<T> node, T value) {
          if(node == null){
              return null;
           }
          else {
              //value is less than node's data then, search the value in left subtree
              if(value.CompareTo(node.data) < 0)
                  node.left = deleteNode(node.left, value);
              
              //value is greater than node's data then, search the value in right subtree
              else if(value.CompareTo(node.data) > 0)
                  node.right = deleteNode(node.right, value);
              
              //If value is equal to node's data that is, we have found the node to be deleted
              else {
                  //If node to be deleted has no child then, set the node to null
                  if(node.left == null && node.right == null)
                      node = null;
                  
                  //If node to be deleted has only one right child
                  else if(node.left == null) {
                      node = node.right;
                  }
                  
                  //If node to be deleted has only one left child
                  else if(node.right == null) {
                      node = node.left;
                  }
                  
                  //If node to be deleted has two children node
                  else {
                      //then find the minimum node from right subtree
                      Node<T> temp = minNode(node.right);
                      //Exchange the data between node and temp
                      node.data = temp.data;
                      //Delete the node duplicate node from right subtree
                      node.right = deleteNode(node.right, temp.data);
                  }
              }
              return node;
          }
        }
        
        //inorder() will perform inorder traversal on binary search tree
        public void inorderTraversal(Node<T> node) {
          
          //Check whether tree is empty
          if(root == null){
              Console.WriteLine("Tree is empty");
              return;
           }
          else {
              
              if(node.left!= null)
                  inorderTraversal(node.left);
              Console.Write(node.data + " ");
              if(node.right!= null)
                  inorderTraversal(node.right);
              
          }      
        }
    }
        
        public static void Main()
        {
            BinarySearchTree<int> bt = new BinarySearchTree<int>();
            //Add nodes to the binary tree
            bt.insert(50);
            bt.insert(30);
            bt.insert(70);
            bt.insert(60);
            bt.insert(10);
            bt.insert(90);
            
            Console.WriteLine("Binary search tree after insertion:");
            //Displays the binary tree
            bt.inorderTraversal(bt.root);
            
            Node<int> deletedNode = null;
            //Deletes node 90 which has no child
            deletedNode = bt.deleteNode(bt.root, 90);
            Console.WriteLine("\nBinary search tree after deleting node 90:");
            bt.inorderTraversal(bt.root);
            
            //Deletes node 30 which has one child
            deletedNode = bt.deleteNode(bt.root, 30);
            Console.WriteLine("\nBinary search tree after deleting node 30:");
            bt.inorderTraversal(bt.root);
            
            //Deletes node 50 which has two children
            deletedNode = bt.deleteNode(bt.root, 50);
            Console.WriteLine("\nBinary search tree after deleting node 50:");
            bt.inorderTraversal(bt.root);                
        }    
    }
}

Output:

Binary search tree after insertion:
10 30 50 60 70 90 
Binary search tree after deleting node 90:
10 30 50 60 70 
Binary search tree after deleting node 30:
10 50 60 70 
Binary search tree after deleting node 50:
10 60 70

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinarySearchTree{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //insert() will add new node to the binary search tree
    function insert($data) {
        //Create a new node
        $newNode = new Node($data);
          
        //Check whether tree is empty
        if($this->root == NULL){
            $this->root = $newNode;
            return;
        }
        else {
            //current node point to root of the tree
            $current = $this->root;
            $parent = NULL;
            
            while(true) {
                //parent keep track of the parent node of current node.
                $parent = $current;
 
                  //If data is less than current's data, node will be inserted to the left of tree
                if($data < $current->data) {
                    $current = $current->left;
                    if($current == NULL) {
                        $parent->left = $newNode;
                          return;
                    }
                }
                //If data is greater than current's data, node will be inserted to the right of tree
                else {
                    $current = $current->right;
                    if($current == NULL) {
                        $parent->right = $newNode;
                        return;
                    }
                }
            }
        }
    }
      
    //minNode() will find out the minimum node
    function minNode($root) {
        if ($root->left != NULL)
            return $this->minNode($root->left);
        else 
            return $root;
    } 
    
    //deleteNode() will delete the given node from the binary search tree
    function deleteNode($node, $value) {
        if($node == NULL){
            return NULL;
        }
        else {
            //value is less than node's data then, search the value in left subtree
            if($value < $node->data)
                $node->left = $this->deleteNode($node->left, $value);
              
            //value is greater than node's data then, search the value in right subtree
            else if($value > $node->data)
                $node->right = $this->deleteNode($node->right, $value);
              
            //If value is equal to node's data that is, we have found the node to be deleted
            else {
                //If node to be deleted has no child then, set the node to null
                if($node->left == NULL && $node->right == NULL)
                    $node = NULL;
                
                //If node to be deleted has only one right child
                else if($node->left == NULL) {
                    $node = $node->right;
                }
                
                //If node to be deleted has only one left child
                else if($node->right == NULL) {
                  $node = $node->left;
                }
                
                //If node to be deleted has two children node
                else {
                    //then find the minimum node from right subtree
                    $temp = $this->minNode($node->right);
                    //Exchange the data between node and temp
                    $node->data = $temp->data;
                    //Delete the node duplicate node from right subtree
                    $node->right = $this->deleteNode($node->right, $temp->data);
                }
            }
            return $node;
        }
    }
      
    //inorder() will perform inorder traversal on binary search tree
    function inorderTraversal($node) {
        
        //Check whether tree is empty
        if($this->root == NULL){
            print("Tree is empty <br>");
            return;
        }
        else {
          
            if($node->left != NULL)
              $this->inorderTraversal($node->left);
            print("$node->data  ");
            if($node->right != NULL)
              $this->inorderTraversal($node->right);
          
        }      
    }
}
$bt = new BinarySearchTree();
//Add nodes to the binary tree
$bt->insert(50);
$bt->insert(30);
$bt->insert(70);
$bt->insert(60);
$bt->insert(10);
$bt->insert(90);
 
print("Binary search tree after insertion: <br>");
//Displays the binary tree
$bt->inorderTraversal($bt->root);
 
//Deletes node 90 which has no child
$deletedNode = $bt->deleteNode($bt->root, 90);
print("<br>Binary search tree after deleting node 90: <br>");
$bt->inorderTraversal($bt->root);
 
//Deletes node 30 which has one child
$deletedNode = $bt->deleteNode($bt->root, 30);
print("<br>Binary search tree after deleting node 30: <br>");
$bt->inorderTraversal($bt->root);
 
//Deletes node 50 which has two children
$deletedNode = $bt->deleteNode($bt->root, 50);
print("<br>Binary search tree after deleting node 50: <br>");
$bt->inorderTraversal($bt->root);
?>
</body>
</html>

Output:

Binary search tree after insertion:
10 30 50 60 70 90 
Binary search tree after deleting node 90:
10 30 50 60 70 
Binary search tree after deleting node 30:
10 50 60 70 
Binary search tree after deleting node 50:
10 60 70

Next TopicPrograms List




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf