×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

Delete nodes greater than or equal to k in a BST

In this article, we are going to see how to delete nodes having value greater than or equal to K? Submitted by Radib Kar, on February 13, 2019

Problem statement

Given a BST and a value x, write a function to delete the nodes having values greater than or equal to x. The function will return the modified root.

Example

Input BST
      8
    /  \
   4    10
  / \   / \
 3   5  9  11

Input X:  10

After deletion:


     8
    /  \
   4    9
  / \   
 3   5  

Solution Approach

Basic properties of BST:

  1. All node values are distinct.
  2. The left child node is always smaller than the root & right child node is always greater than the root.

Thus it's clear whenever a root has a value greater than or equal to the input value X, the entire right subtree and root need to be deleted, but not the left one.

Algorithm

FUNCTION buildTree (root,X)
    IF (root==NULL)
        Return NULL;
    END IF
    IF (root->data is equal to X)
        return root->left; //returning the left subtree basically
    ELSE IF(root->data>key)
        //recur for the left subtree since left subtree may also have nodes 
        //that need to be deleted due to greater or equal values
        return buildTree(root->left, X); 
    ELSE
        //root is not at all to be deleted, same for left subtree, 
        //recursively process right subtree
        root->right=buildTree(root->right, X);
        return root;
END FUNCTION

The above function actually builds the tree deleting the nodes having greater and equal value than X.

Explanation with example

Nodes are represented by respected values for better understanding
      8
    /  \
   4    10
  / \   / \
 3   5  9  11

Input X:  10

At main we callbuildTree (8, 10)
------------------------------------------------

buildTree (8, 10)
root not NULL
8<10
Thus root->left= 8->left
root->right=buildTree (8->right, 10) //buildTree (10, 10)
------------------------------------------------

buildTree (10, 10)
root not NULL
10==10
Thus return root->left= 10->left=9
------------------------------------------------

Hence At buildTree (8, 10)
Thus root->left= 8->left
root->right=9 (9 is the root to the remaining subtree which is NULL here luckily)

So the tree actually becomes
     8
   / \
  4     9
 / \ 
3   5 

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Node{
	public:             
	int data;           //value
	Node *left;    //pointer to left child
	Node *right;   //pointer to right child
};

// creating new node
Node* newnode(int data)  
{ 
	Node* node = (Node*)malloc(sizeof(Node)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 
	return(node); 
}

Node* buildTree(Node* root,int key){
	if(!root)
		return NULL;
	if(root->data==key){
		return root->left; //only left subtree not deleted
	}
	else if(root->data>key)
		return buildTree(root->left,key); //recur for left subtree
	else{
		//root not deleted
		//left subtree not deleted
		//buld right subtree
		root->right=buildTree(root->right,key); 
		return root;
	}
}

Node* deleteNode(Node* root, int key)
{
	root=buildTree(root,key);
	return root; 
}

void levelwisedisplay(Node *root)
{
	//to display the tree level wise
	queue<Node*> q;

	Node* temp;
	int count=0;
	q.push(root);
	q.push(NULL);

	while(!q.empty()){
		temp=q.front();
		q.pop();

		if(temp==NULL){
			if(!q.empty())
				q.push(NULL);
			cout<<"\nend of level "<<count++<<endl;
		}
		else{
			cout<<temp->data<<" ";
			if(temp->left)
				q.push(temp->left);
			if(temp->right)
				q.push(temp->right);
		}
	}
	return ;
}

int main(){
	cout<<"tree is built as per example\n";

	Node *root=newnode(8); 
	root->left= newnode(4); 
	root->right= newnode(10); 
	root->right->right=newnode(11);
	root->right->left=newnode(9);
	root->left->left=newnode(3); 
	root->left->right=newnode(5);

	printf("Displaying level wise\n");
	levelwisedisplay(root);

	root=deleteNode(root,10);//as per example

	printf("after deleting nodes greater or equal to 10\n");
	levelwisedisplay(root);

	return 0;
}

Output

tree is built as per example
Displaying level wise
8      
end of level 0
4 10   
end of level 1
3 5 9 11      
end of level 2
after deleting nodes greater or equal to 10
8      
end of level 0
4 9    
end of level 1
3 5    
end of level 2 


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.