Skip to main content

Delete sorted sequence in Binary Search Tree

Delete sorted sequence in BST

Here given code implementation process.

//C Program 
//Delete sorted sequence in Binary Search Tree
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}

int binary_search(int *arr,int size,int element)
{

  if(size <= 1) return -1;

  int i=0, j = (size-1),mid=0;
 
  //base condition
  while(j > i && arr[i] != element && arr[j] != element)
  {
    //Get middle element
    mid = (i+j)/2;

    if(arr[mid] > element)
    {
      //When middle element of index i and j are greater
      j = mid-1;
    }
    else if(arr[mid] < element)
    {
      //When middle element of index i and j are less
      i = mid+1;
    }
    else
    {
      //when get element
      i = mid;
      break;
    }
  }
  if(arr[i] == element )
  {
  
     return i;

  }
  else if(arr[j] == element )
  {
     return j;
  }
  return -1;
}
//Swap two nodes values
void swap_data(struct Node*root1, struct Node*root2)
{
  int temp=root1->data;
  root1->data=root2->data;
  root2->data=temp;
}
struct Node* delete_elements(struct Node*root,
 struct Node*left_side,
 struct Node*right_side,
 int collection[],
 int size
 )
{
  if(root != NULL)
  {

   root->left = delete_elements(root->left,left_side,root,collection,size);
   root->right = delete_elements(root->right,root,right_side,collection,size);
   
   if(binary_search(collection,size,root->data)!=-1)
   {
     
     if(root->left == NULL && root->right == NULL )
     {
      //Delete leaf node
      free(root);
      root=NULL;
     }
     else if(root->left == NULL)
     {
       right_side=root->right;
       free(root);
       root=right_side;
     }
     else if(root->right==NULL)
     {
        left_side=root->left;
       free(root);
       root=left_side;
     }
   }
   else if(left_side != NULL && binary_search(collection,size,left_side->data)!=-1)
   {

     //Swap element values
     swap_data(left_side,root);
     right_side=root->right;
     free(root);
     root=right_side;

   } 
   else if(right_side != NULL && binary_search(collection,size,right_side->data)!=-1)
   {
    //swap element values
     swap_data(right_side,root);
     left_side=root->left;
     free(root);
     root=left_side;
   }
  }

  return root;
}
struct Node* delete_collection(struct Node*root,
  int collection[],
  int size)
{
  if(root != NULL)
  {
    
   return delete_elements(root,NULL,NULL,collection,size);

  }
  else
  {
    printf("Empty BST\n");
    return NULL;
  }
 
}

void preorder(struct Node*root)
{
  if(root!=NULL)
  {
    printf("%3d ",root->data );
    preorder(root->left);

    preorder(root->right);
  }
}
int main(){
    
  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


  */                


    add(&root,5); 
    add(&root,3); 
    add(&root,9); 
    add(&root,1); 
    add(&root,4); 
    add(&root,8); 
    add(&root,11); 
    add(&root,-3); 
    add(&root,2); 
    add(&root,7); 
    add(&root,12); 
    preorder(root);//Before Delete

    int sort_collection[]={1,5,7,9,12};

    int size = sizeof(sort_collection)/sizeof(sort_collection[0]);
  
    root=delete_collection(root,sort_collection,size);
   
    printf("\n");
    preorder(root);//After Delete


  return 0;
}

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
/*
  C++ Program
  Delete sorted sequence in Binary Search Tree
*/

#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
public:
  Node *root;
  BinarySearchTree() {
    this->root = NULL;
  }
  void add(int value) {
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        this->root = new_node;
      } else {
        Node *find = this->root;
        while (find != NULL) {
          if (find->data >= value) {
            if (find->left == NULL) {
              find->left = new_node;
              break;
            } else {
              find = find->left;
            }
          } else {
            if (find->right == NULL) {
              find->right = new_node;
              break;
            } else {
              find = find->right;
            }
          }
        }
      }
    } else {
      cout << "\nMemory Overflow\n";
    }
  }
  void preorder(Node *head) {
    if (head != NULL) {
      cout << head->data << "  ";
      this->preorder(head->left);
      this->preorder(head->right);
    }
  }
  void swap_data(Node *root1, Node *root2) {
    int temp = root2->data;
    root2->data = root1->data;
    root1->data = temp;
  }
  int binary_search(int arr[], int size, int element) {
    int i = 0, j = size - 1, mid = 0;
    while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
      mid = (i + j) / 2;
      if (arr[mid] > element) {
        j = mid - 1;
      } else
      if (arr[mid] < element) {
        i = mid + 1;
      } else {
        i = mid;
        break;;
      }
    }
    if (i != -1 && arr[i] == element) {
      return i;
    } else
    if (j != -1 && arr[j] == element) {
      return j;
    }
    return -1;
  }
  Node *delete_elements(Node *head, Node *left_side, Node *right_side, int collection[], int size) {
    if (head != NULL) {
      head->left = this->delete_elements(head->left, left_side, head, collection, size);
      head->right = this->delete_elements(head->right, head, right_side, collection, size);
      if (this->binary_search(collection, size, head->data) != -1) {
        if (head->left == NULL && head->right == NULL) {
          head = NULL;
        } else
        if (head->left == NULL) {
          right_side = head->right;
          head = right_side;
        } else
        if (head->right == NULL) {
          left_side = head->left;
          head = left_side;
        }
      } else
      if (left_side != NULL && this->binary_search(collection, size, left_side->data) != -1) {
        this->swap_data(left_side, head);
        right_side = head->right;
        head = right_side;
      } else
      if (right_side != NULL && this->binary_search(collection, size, right_side->data) != -1) {
        this->swap_data(right_side, head);
        left_side = head->left;
        head = left_side;
      }
    }
    return head;
  }
  void delete_collection(int collection[], int size) {
    if (this->root != NULL) {
      this->root = this->delete_elements(this->root, NULL, NULL, collection, size);
    } else {
      cout << "Empty BST\n";
    }
  }
};

int main() {
  BinarySearchTree obj ;
  //Add nodes in binary search tree
  /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


  */  
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(8);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(7);
  obj.add(12);
  obj.preorder(obj.root);
  int sort_collection[] = { 1, 5, 7, 9, 12 };
  int size = sizeof(sort_collection)/sizeof(sort_collection[0]);
  obj.delete_collection(sort_collection, size);
  cout << "\n";
  obj.preorder(obj.root);
  return 0;
}

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
//Java program
//Delete sorted sequence in Binary search tree

//BST node
class Node {

  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;


  public BinarySearchTree() {
    root = null;

  }
  //insert a node in BST
  public void add(int value) {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if (new_node != null) {
      if (root == null) {
        //When adds a first node in binary tree
        root = new_node;
      } else {
        Node find = root;

        //add new node to proper position
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              break;
            } else {
              //visit left sub-tree
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              break;
            } else {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    } else {
      System.out.print("\nMemory Overflow\n");
    }
  }

  public void preorder(Node head) {
    if (head != null) {
      System.out.print(head.data + "  ");
      preorder(head.left);

      preorder(head.right);
    }
  }
  public void swap_data(Node root1, Node root2) {
    int temp = root2.data;
    root2.data = root1.data;
    root1.data = temp;
  }

  //Method which is finding given element index
  public int binary_search(int[] arr, int size, int element) {
    int i = 0, j = size - 1, mid = 0;

    //base condition
    while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
      //Get middle element
      mid = (i + j) / 2;

      if (arr[mid] > element) {
        //When middle element of index i and j are greater
        j = mid - 1;
      } else if (arr[mid] < element) {
        //When middle element of index i and j are less
        i = mid + 1;
      } else {
        //when get element
        i = mid;
        break;
      }
    }
    if (i != -1 && arr[i] == element) {
      return i;

    } else if (j != -1 && arr[j] == element) {
      return j;
    }

    return -1;
  }

  public Node delete_elements(Node head,
    Node left_side,
    Node right_side,
    int[] collection,
    int size
  ) {
    if (head != null) {

      head.left = delete_elements(head.left, left_side, head, collection, size);
      head.right = delete_elements(head.right, head, right_side, collection, size);

      if (binary_search(collection, size, head.data) != -1) {

        if (head.left == null && head.right == null) {
          //Delete leaf node
          head = null;
        } else if (head.left == null) {
          right_side = head.right;

          head = right_side;
        } else if (head.right == null) {
          left_side = head.left;

          head = left_side;
        }
      } else if (left_side != null && binary_search(collection, size, left_side.data) != -1) {

        //Swap element values
        swap_data(left_side, head);
        right_side = head.right;

        head = right_side;

      } else if (right_side != null && binary_search(collection, size, right_side.data) != -1) {
        //swap element values
        swap_data(right_side, head);
        left_side = head.left;

        head = left_side;
      }
    }

    return head;
  }
  public void delete_collection(int collection[],
    int size) {
    if (root != null) {

      root = delete_elements(root, null, null, collection, size);

    } else {
      System.out.print("Empty BST\n");

    }

  }
  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();

    //Add nodes in binary search tree
    /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12
    */


    obj.add(5);
    obj.add(3);
    obj.add(9);
    obj.add(1);
    obj.add(4);
    obj.add(8);
    obj.add(11);
    obj.add(-3);
    obj.add(2);
    obj.add(7);
    obj.add(12);

    obj.preorder(obj.root); //Before Delete

    int[] sort_collection = { 1, 5, 7, 9, 12  };

    int size = sort_collection.length;

    obj.delete_collection(sort_collection, size);

    System.out.print("\n");

    obj.preorder(obj.root); //After Delete
  }
}

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
//C# program
//Delete sorted sequence in Binary search tree
using System;
//BST node
public class Node {

	public int data;
	public Node left;
	public Node right;

	public Node(int value) {
		data = value;
		left = null;
		right = null;
	}
}
public class BinarySearchTree {


	public Node root;


	public BinarySearchTree() {
		root = null;

	}
	//insert a node in BST
	public void add(int value) {
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);

		if (new_node != null) {
			if (root == null) {
				//When adds a first node in binary tree
				root = new_node;
			} else {
				Node find = root;

				//add new node to proper position
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;
						} else {
							//visit left sub-tree
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;
						} else {
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		} else {
			Console.Write("\nMemory Overflow\n");
		}
	}

	public void preorder(Node head) {
		if (head != null) {
			Console.Write(head.data + "  ");
			preorder(head.left);

			preorder(head.right);
		}
	}
	public void swap_data(Node root1, Node root2) {
		int temp = root2.data;
		root2.data = root1.data;
		root1.data = temp;
	}

	//Method which is finding given element index
	public int binary_search(int[] arr, int size, int element) {
		int i = 0, j = size - 1, mid = 0;

		//base condition
		while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
			//Get middle element
			mid = (i + j) / 2;

			if (arr[mid] > element) {
				//When middle element of index i and j are greater
				j = mid - 1;
			} else if (arr[mid] < element) {
				//When middle element of index i and j are less
				i = mid + 1;
			} else {
				//when get element
				i = mid;
				break;
			}
		}
		if (i != -1 && arr[i] == element) {
			return i;

		} else if (j != -1 && arr[j] == element) {
			return j;
		}

		return -1;
	}

	public Node delete_elements(Node head,
		Node left_side,
		Node right_side,
		int[] collection,
		int size
	) {
		if (head != null) {

			head.left = delete_elements(head.left, left_side, head, collection, size);
			head.right = delete_elements(head.right, head, right_side, collection, size);

			if (binary_search(collection, size, head.data) != -1) {

				if (head.left == null && head.right == null) {
					//Delete leaf node
					head = null;
				} else if (head.left == null) {
					right_side = head.right;

					head = right_side;
				} else if (head.right == null) {
					left_side = head.left;

					head = left_side;
				}
			} else if (left_side != null && binary_search(collection, size, left_side.data) != -1) {

				//Swap element values
				swap_data(left_side, head);
				right_side = head.right;

				head = right_side;

			} else if (right_side != null && binary_search(collection, size, right_side.data) != -1) {
				//swap element values
				swap_data(right_side, head);
				left_side = head.left;

				head = left_side;
			}
		}

		return head;
	}
	public void delete_collection(int []collection,
		int size) {
		if (root != null) {

			root = delete_elements(root, null, null, collection, size);

		} else {
			Console.Write("Empty BST\n");

		}

	}
	public static void Main(String[] args) {

		BinarySearchTree obj = new BinarySearchTree();

		//Add nodes in binary search tree
		/*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12
    */


		obj.add(5);
		obj.add(3);
		obj.add(9);
		obj.add(1);
		obj.add(4);
		obj.add(8);
		obj.add(11);
		obj.add(-3);
		obj.add(2);
		obj.add(7);
		obj.add(12);

		obj.preorder(obj.root); //Before Delete

		int[] sort_collection = { 1, 5, 7, 9, 12  };

		int size = sort_collection.Length;

		obj.delete_collection(sort_collection, size);

		Console.Write("\n");

		obj.preorder(obj.root); //After Delete
	}
}

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
#  Python 3 Program
#  Delete sorted sequence in Binary Search Tree

class Node :
  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :

  def __init__(self) :
    self.root = None
  
  def add(self, value) :
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        self.root = new_node
      else :
        find = self.root
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              break
            else :
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              break
            else :
              find = find.right
            
          
        
      
    else :
      print("\nMemory Overflow\n")
    
  
  def preorder(self, head) :
    if (head != None) :
      print(head.data ,end="  ")
      self.preorder(head.left)
      self.preorder(head.right)
    
  
  def swap_data(self, root1, root2) :
    temp = root2.data
    root2.data = root1.data
    root1.data = temp
  
  def binary_search(self, arr, size, element) :
    i = 0
    j = size - 1
    mid = 0
    while (j > 0 and j > i and arr[i] != element and arr[j] != element) :
      mid = int((i + j) / 2)
      if (arr[mid] > element) :
        j = mid - 1
      elif (arr[mid] < element) :
        i = mid + 1
      else :
        i = mid
        break
      
    
    if (i != -1 and arr[i] == element) :
      return i
    elif (j != -1 and arr[j] == element) :
      return j
    
    return -1
  
  def delete_elements(self, head, left_side, right_side, collection, size) :
    if (head != None) :
      head.left = self.delete_elements(head.left, left_side, head, collection, size)
      head.right = self.delete_elements(head.right, head, right_side, collection, size)
      if (self.binary_search(collection, size, head.data) != -1) :
        if (head.left == None and head.right == None) :
          head = None
        elif (head.left == None) :
          right_side = head.right
          head = right_side
        elif (head.right == None) :
          left_side = head.left
          head = left_side
        
      elif (left_side != None and self.binary_search(collection, size, left_side.data) != -1) :
        self.swap_data(left_side, head)
        right_side = head.right
        head = right_side
      elif (right_side != None and self.binary_search(collection, size, right_side.data) != -1) :
        self.swap_data(right_side, head)
        left_side = head.left
        head = left_side
      
    
    return head
  
  def delete_collection(self, collection, size) :
    if (self.root != None) :
      self.root = self.delete_elements(self.root, None, None, collection, size)
    else :
      print("Empty BST\n")
    
  
def main() :
  obj = BinarySearchTree()
  #
  #           5
  #         /    \
  #        3      9
  #       / \     / \
  #      1   4   8   11
  #     / \     /      \
  #    -3  2   7        12
  #  
  obj.add(5)
  obj.add(3)
  obj.add(9)
  obj.add(1)
  obj.add(4)
  obj.add(8)
  obj.add(11)
  obj.add(-3)
  obj.add(2)
  obj.add(7)
  obj.add(12)
  obj.preorder(obj.root)
  sort_collection = [1, 5, 7, 9, 12]
  size = len(sort_collection)
  obj.delete_collection(sort_collection, size)
  print()
  obj.preorder(obj.root)
  

if __name__ == "__main__":
  main()

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
# Ruby Program
# Delete sorted sequence in Binary Search Tree

class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinarySearchTree 
	attr_reader :root
	attr_accessor :root
	def initialize() 
		@root = nil
	end
	def add(value) 
		new_node = Node.new(value)
		if (new_node != nil) 
			if (@root == nil) 
				@root = new_node
			else 
				find = @root
				while (find != nil) 
					if (find.data >= value) 
						if (find.left == nil) 
							find.left = new_node
							break
						else 
							find = find.left
						end
					else 
						if (find.right == nil) 
							find.right = new_node
							break
						else 
							find = find.right
						end
					end
				end
			end
		else 
			print("\nMemory Overflow\n")
		end
	end
	def preorder(head) 
		if (head != nil) 
			print(head.data ,"  ")
			self.preorder(head.left)
			self.preorder(head.right)
		end
	end
	def swap_data(root1, root2) 
		temp = root2.data
		root2.data = root1.data
		root1.data = temp
	end
	def binary_search(arr, size, element) 
		i = 0
		j = size - 1
		mid = 0
		while (j > 0 and j > i and arr[i] != element and arr[j] != element) 
			mid = (i + j) / 2
			if (arr[mid] > element) 
				j = mid - 1
			elsif (arr[mid] < element) 
				i = mid + 1
			else 
				i = mid
				break
			end
		end
		if (i != -1 and arr[i] == element) 
			return i
		elsif (j != -1 and arr[j] == element) 
			return j
		end
		return -1
	end
	def delete_elements(head, left_side, right_side, collection, size) 
		if (head != nil) 
			head.left = self.delete_elements(head.left, left_side, head, collection, size)
			head.right = self.delete_elements(head.right, head, right_side, collection, size)
			if (self.binary_search(collection, size, head.data) != -1) 
				if (head.left == nil and head.right == nil) 
					head = nil
				elsif (head.left == nil) 
					right_side = head.right
					head = right_side
				elsif (head.right == nil) 
					left_side = head.left
					head = left_side
				end
			elsif (left_side != nil and self.binary_search(collection, size, left_side.data) != -1) 
				self.swap_data(left_side, head)
				right_side = head.right
				head = right_side
			elsif (right_side != nil and self.binary_search(collection, size, right_side.data) != -1) 
				self.swap_data(right_side, head)
				left_side = head.left
				head = left_side
			end
		end
		return head
	end
	def delete_collection(collection, size) 
		if (@root != nil) 
			@root = self.delete_elements(@root, nil, nil, collection, size)
		else 
			print("Empty BST\n")
		end
	end
end
def main() 
	obj = BinarySearchTree.new()
	#
	#           5
	#         /    \
	#        3      9
	#       / \     / \
	#      1   4   8   11
	#     / \     /      \
	#    -3  2   7        12
	#  
	obj.add(5)
	obj.add(3)
	obj.add(9)
	obj.add(1)
	obj.add(4)
	obj.add(8)
	obj.add(11)
	obj.add(-3)
	obj.add(2)
	obj.add(7)
	obj.add(12)
	obj.preorder(obj.root)
	sort_collection = [1, 5, 7, 9, 12]
	size = sort_collection.length
	obj.delete_collection(sort_collection, size)
	print("\n")
	obj.preorder(obj.root)
end

main()

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
<?php
/*
  Php Program
  Delete sorted sequence in Binary Search Tree
*/

class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function add($value) {
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        $this->root = $new_node;
      } else {
        $find = $this->root;
        while ($find != null) {
          if ($find->data >= $value) {
            if ($find->left == null) {
              $find->left = $new_node;
              break;
            } else {
              $find = $find->left;
            }
          } else {
            if ($find->right == null) {
              $find->right = $new_node;
              break;
            } else {
              $find = $find->right;
            }
          }
        }
      }
    } else {
      echo("\nMemory Overflow\n");
    }
  }
  public  function preorder($head) {
    if ($head != null) {
      echo($head->data ."  ");
      $this->preorder($head->left);
      $this->preorder($head->right);
    }
  }
  public  function swap_data($root1, $root2) {
    $temp = $root2->data;
    $root2->data = $root1->data;
    $root1->data = $temp;
  }
  public  function binary_search($arr, $size, $element) {
    $i = 0;
    $j = $size - 1;
    $mid = 0;
    while ($j > 0 && $j > $i && $arr[$i] != $element && $arr[$j] != $element) {
      $mid = intval(($i + $j) / 2);
      if ($arr[$mid] > $element) {
        $j = $mid - 1;
      } else if ($arr[$mid] < $element) {
        $i = $mid + 1;
      } else {
        $i = $mid;
        break;
      }
    }
    if ($i != -1 && $arr[$i] == $element) {
      return $i;
    } 
    else if ($j != -1 && $arr[$j] == $element) {
      return $j;
    }
    return -1;
  }
  public  function delete_elements($head, $left_side, $right_side, $collection, $size) {
    if ($head != null) {
      $head->left = $this->delete_elements($head->left, $left_side, $head, $collection, $size);
      $head->right = $this->delete_elements($head->right, $head, $right_side, $collection, $size);
      if ($this->binary_search($collection, $size, $head->data) != -1) {
        if ($head->left == null && $head->right == null) {
          $head = null;
        } else
        if ($head->left == null) {
          $right_side = $head->right;
          $head = $right_side;
        } else
        if ($head->right == null) {
          $left_side = $head->left;
          $head = $left_side;
        }
      } else
      if ($left_side != null && $this->binary_search($collection, $size, $left_side->data) != -1) {
        $this->swap_data($left_side, $head);
        $right_side = $head->right;
        $head = $right_side;
      } else
      if ($right_side != null && $this->binary_search($collection, $size, $right_side->data) != -1) {
        $this->swap_data($right_side, $head);
        $left_side = $head->left;
        $head = $left_side;
      }
    }
    return $head;
  }
  public  function delete_collection($collection, $size) {
    if ($this->root != null) {
      $this->root = $this->delete_elements($this->root, null, null, $collection, $size);
    } else {
      echo ("Empty BST\n");
    }
  }
}
function main() {
  $obj = new BinarySearchTree();
  //Binary search tree
  /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


  */  
  $obj->add(5);
  $obj->add(3);
  $obj->add(9);
  $obj->add(1);
  $obj->add(4);
  $obj->add(8);
  $obj->add(11);
  $obj->add(-3);
  $obj->add(2);
  $obj->add(7);
  $obj->add(12);
  $obj->preorder($obj->root);
  $sort_collection = array(1, 5, 7, 9, 12);
  $size = count($sort_collection);
  $obj->delete_collection($sort_collection, $size);
  echo ("\n");
  $obj->preorder($obj->root);
}
main();

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
/*
	Node Js Program
	Delete sorted sequence in Binary Search Tree
*/

class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree {
	
	constructor() {
		this.root = null;
	}
	add(value) {
		var new_node = new Node(value);
		if (new_node != null) {
			if (this.root == null) {
				this.root = new_node;
			} else {
				var find = this.root;
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;;
						} else {
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;;
						} else {
							find = find.right;
						}
					}
				}
			}
		} else {
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	preorder(head) {
		if (head != null) {
			process.stdout.write(head.data + "  ");
			this.preorder(head.left);
			this.preorder(head.right);
		}
	}
	swap_data(root1, root2) {
		var temp = root2.data;
		root2.data = root1.data;
		root1.data = temp;
	}
	binary_search(arr, size, element) {
		var i = 0;
		var j = size - 1;
		var mid = 0;
		while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
			mid = (i + j) / 2;
			if (arr[mid] > element) {
				j = mid - 1;
			} else
			if (arr[mid] < element) {
				i = mid + 1;
			} else {
				i = mid;
				break;;
			}
		}
		if (i != -1 && arr[i] == element) {
			return i;
		} else
		if (j != -1 && arr[j] == element) {
			return j;
		}
		return -1;
	}
	delete_elements(head, left_side, right_side, collection, size) {
		if (head != null) {
			head.left = this.delete_elements(head.left, left_side, head, collection, size);
			head.right = this.delete_elements(head.right, head, right_side, collection, size);
			if (this.binary_search(collection, size, head.data) != -1) {
				if (head.left == null && head.right == null) {
					head = null;
				} else
				if (head.left == null) {
					right_side = head.right;
					head = right_side;
				} else
				if (head.right == null) {
					left_side = head.left;
					head = left_side;
				}
			} else
			if (left_side != null && this.binary_search(collection, size, left_side.data) != -1) {
				this.swap_data(left_side, head);
				right_side = head.right;
				head = right_side;
			} else
			if (right_side != null && this.binary_search(collection, size, right_side.data) != -1) {
				this.swap_data(right_side, head);
				left_side = head.left;
				head = left_side;
			}
		}
		return head;
	}
	delete_collection(collection, size) {
		if (this.root != null) {
			this.root = this.delete_elements(this.root, null, null, collection, size);
		} else {
			process.stdout.write("Empty BST\n");
		}
	}
}

function main() {
	var obj = new BinarySearchTree();
	//Binary search tree
	/*
	         5
	       /    \
	      3      9
	     / \     / \
	    1   4   8   11
	   / \     /      \
	  -3  2   7        12


	*/  
	obj.add(5);
	obj.add(3);
	obj.add(9);
	obj.add(1);
	obj.add(4);
	obj.add(8);
	obj.add(11);
	obj.add(-3);
	obj.add(2);
	obj.add(7);
	obj.add(12);
	obj.preorder(obj.root);
	var sort_collection = [1, 5, 7, 9, 12];
	var size = sort_collection.length;
	obj.delete_collection(sort_collection, size);
	process.stdout.write("\n");
	obj.preorder(obj.root);
}

main();

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 
/*
  Swift 4 Program
  Delete sorted sequence in Binary Search Tree
*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func preorder(_ head: Node? ) {
    if (head != nil) {
      print(head!.data ,terminator:"  ");
      self.preorder(head!.left);
      self.preorder(head!.right);
    }
  }
  func swap_data(_ root1: Node? , _ root2 : Node? ) {
    let temp: Int = root2!.data;
    root2!.data = root1!.data;
    root1!.data = temp;
  }
  func binary_search(_ arr: [Int] , _ size : Int, _ element: Int) -> Int {
    var i: Int = 0;
    var j = size - 1;
    var mid = 0;
    while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
      mid = ((i + j) / 2);
      if (arr[mid] > element) {
        j = mid - 1;
      } else
      if (arr[mid] < element) {
        i = mid + 1;
      } else {
        i = mid;
        break;
      }
    }
    if (i != -1 && arr[i] == element) {
      return i;
    } else
    if (j != -1 && arr[j] == element) {
      return j;
    }
    return -1;
  }
  func delete_elements(_ element: Node? , _ left_s : Node? , _ right_s : Node? , _ collection : [Int] , _ size : Int) -> Node? {
    var head : Node? = element;

    var left_side : Node? = left_s;

    var right_side : Node? = right_s;

    if (head != nil) {
      head!.left = self.delete_elements(head!.left, left_side, head, collection, size);
      head!.right = self.delete_elements(head!.right, head, right_side, collection, size);
      if (self.binary_search(collection, size, head!.data) != -1) {
        if (head!.left == nil && head!.right == nil) {
          head = nil;
        } else
        if (head!.left == nil) {
          right_side = head!.right;
          head = right_side;
        } else
        if (head!.right == nil) {
          left_side = head!.left;
          head = left_side;
        }
      } else
      if (left_side != nil && self.binary_search(collection, size, left_side!.data) != -1) {
        self.swap_data(left_side, head);
        right_side = head!.right;
        head = right_side;
      } else
      if (right_side != nil && self.binary_search(collection, size, right_side!.data) != -1) {
        self.swap_data(right_side, head);
        left_side = head!.left;
        head = left_side;
      }
    }
    return head;
  }
  func delete_collection(_ collection: [Int], _ size: Int) {
    if (self.root != nil) {
      self.root = self.delete_elements(self.root, nil, nil, collection, size);
    } else {
      print("Empty BST\n");
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  //Binary search tree
  /*
           5
         /    \
        3      9
       / \     / \
      1   4   8   11
     / \     /      \
    -3  2   7        12
  */  
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(8);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(7);
  obj.add(12);
  obj.preorder(obj.root);
  let sort_collection: [Int] = [1, 5, 7, 9, 12];
  let size: Int = sort_collection.count;
  obj.delete_collection(sort_collection, size);
  print();
  obj.preorder(obj.root);
}
main();

Output

  5   3   1  -3   2   4   9   8   7  11  12 
  4   3  -3   2   8  11 




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment