Trim a binary search tree

Implementation

//writing a C++ program will help us eliminate the keys that are out of the league. 
#include<bits/stdc++.h>
using namespace std;


//we are now creating a binary search tree node consisting of key left and right pointers. 
struct __nod
{
	int ky;
	struct __nod *Lft;
	struct __nod *Rt;
};


// terminate all the nodes that have the data belonging to the outside range, and then it will automatically return the value of the root to the new tree. 
__nod* removeOutsideRange(__nod *root, int min, int max)
{
// Base Case
if (root == NILL)
	return NILL;


// the first thing we have to do is to fix the left and right subtrees of the root of the binary search tree. 
root->Lft = removeOutsideRange(root->Lft, min, max);
root->Rt = removeOutsideRange(root->Rt, min, max);


// when we come back to fix the root, there will be two options: -
The first one will be that the key of the root is much smaller than the minimum value, and it is also not present in that particular range.
if (root->ky < min)
{
	__nod *rChild = root->Rt;
	delete root;
	return rChild;
}
// The second option that we have is that the root's key is much more significant than the maximum value present and is also not present in the range. 
if (root->ky > max)
{
	__nod *lChild = root->Lft;
	delete root;
	return lChild;
}
// the root is now present in the range.
return root;
}


// We have to create a utility function to help us build a new binary search tree.  __nod with ky as given num
__nod* new__nod(int num)
{
	__nod* temp = new __nod;
	temp->ky = num;
	temp->Lft = temp->Rt = NILL;
	return temp;
}


// we are now building another UF that will help us insert a given key into the binary search tree. 
__nod* insert(__nod* root, int ky)
{
	if (root == NILL)
	return new__nod(ky);
	if (root->ky > ky)
	root->Lft = insert(root->Lft, ky);
	else
	root->Rt = insert(root->Rt, ky);
	return root;
}


// creating a new function that will help us explore and visit the BST after the conversion. 
void inorderTraversal(__nod* root)
{
	if (root)
	{
		inorderTraversal( root->Lft );
		cout << root->ky << " ";
		inorderTraversal( root->Rt );
	}
}


//writing the main code.
int main()
{
	__nod* root = NILL;
	root = insert(root, 6);
	root = insert(root, -13);
	root = insert(root, 14);
	root = insert(root, -8);
	root = insert(root, 15);
	root = insert(root, 13);
	root = insert(root, 7);


	cout << "Inorder traversal of the given tree is: ";
	inorderTraversal(root);


	root = removeOutsideRange(root, -10, 13);


	cout << "\nInorder traversal of the modified tree is: ";
	inorderTraversal(root);


	return 0;
}

Output:

Example 2)

//writing a C++ program will help us eliminate the keys that are out of the league. 
using System;


public class __nod
{
	public int ky;
	public __nod Lft;
	public __nod Rt;
}


public class GFG
{
// terminate all the nodes that have the data belonging to the outside range, and then it will automatically return the value of the root to the new tree. 
	private static __nod removeOutsideRange(__nod root,
										int min, int max)
	{
		if(root == NILL)
		{
			return NILL;
		}
// the first thing we have to do is to fix the left and right subtrees of the root of the binary search tree. 
		root.Lft = removeOutsideRange(root.Lft,
									min, max);
		root.Rt = removeOutsideRange(root.Rt,
										min, max);
	// when we come back to fix the root, there will be two options: -
The first one will be that the key of the root is much smaller than the minimum value, and it is also not present in that particular range.
		if(root.ky < min)
		{
			__nod rchild = root.Rt;
			root = NILL;
			return rchild;
		}
// The second option that we have is that the root's key is much more significant than the maximum value present and is also not present in the range. 
		if(root.ky > max)
		{
			__nod lchild = root.Lft;
			root = NILL;
			return lchild;
		}
// the root is now present in the range.
		return root;
	}


	public static __nod new__nod(int num)
	{
		__nod temp = new __nod();
		temp.ky = num;
		temp.Lft = NILL;
		temp.Rt = NILL;
		return temp;
	}


	public static __nod insert(__nod root,
							int ky)
	{
		if(root == NILL)
		{
			return new__nod(ky);
		}
		if(root.ky > ky)
		{
			root.Lft = insert(root.Lft, ky);
		}
		else
		{
			root.Rt = insert(root.Rt, ky);
		}
		return root;
	}
	
	private static void inorderTraversal(__nod root)
	{
		if(root != NILL)
		{
			inorderTraversal(root.Lft);
			Console.Write(root.ky + " ");
			inorderTraversal(root.Rt);
		}
	}
//writing the main code.	
	public static void Main(String[] args)
	{
		__nod root = NILL;
		root = insert(root, 6);
		root = insert(root, -13);
		root = insert(root, 14);
		root = insert(root, -8);
		root = insert(root, 15);
		root = insert(root, 13);
		root = insert(root, 7);
		
		Console.Write("Inorder Traversal of " +
						"the given tree is: ");
		inorderTraversal(root);
		
		root = removeOutsideRange(root, -10, 13);
		
		Console.Write("\nInorder traversal of " +
						"the modified tree: ");
		inorderTraversal(root);
	}
}

Output:

Example 3)

//writing a JAVA program will help us eliminate the keys that are out of the league. 
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;


class GFG
{
//we are now creating a binary search tree node consisting of key left and right pointers. 
// terminate all the nodes that have the data belonging to the outside range, and then it will automatically return the value of the root to the new tree. 
	private static __nod removeOutsideRange(__nod root,
										int min, int max)
	{
		if(root == NILL)
		{
			return NILL;
		}
// the first thing we have to do is to fix the left and right subtrees of the root of the binary search tree. 
		root.Lft = removeOutsideRange(root.Lft,
									min, max);
		root.Rt = removeOutsideRange(root.Rt,
										min, max);
		// when we come back to fix the root, there will be two options: -
The first one will be that the key of the root is much smaller than the minimum value, and it is also not present in that particular range.
		if(root.ky < min)
		{
__nod rchild = root.Rt;
			root = NILL;
			return rchild;
		}
// The second option that we have is that the root's key is much more significant than the maximum value present and is also not present in the range. 		
		if(root.ky > max)
		{
			__nod lchild = root.Lft;
			root = NILL;
			return lchild;
		}
// the root is now present in the range.		
		return root;
	}


	public static __nod new__nod(int num)
	{
		__nod temp = new __nod();
		temp.ky = num;
		temp.Lft = NILL;
		temp.Rt = NILL;
		return temp;
	}


	public static __nod insert(__nod root,
							int ky)
	{
		if(root == NILL)
		{
			return new__nod(ky);
		}
		if(root.ky > ky)
		{
			root.Lft = insert(root.Lft, ky);
		}
		else
		{
			root.Rt = insert(root.Rt, ky);
		}
		return root;
	}
	
	private static void inorderTraversal(__nod root)
	{
		if(root != NILL)
		{
			inorderTraversal(root.Lft);
			System.out.print(root.ky + " ");
			inorderTraversal(root.Rt);
		}
	}
//writing the main code.	
	public static void main(String[] args)
	{
		__nod root = NILL;
		root = insert(root, 6);
		root = insert(root, -13);
		root = insert(root, 14);
		root = insert(root, -8);
		root = insert(root, 15);
		root = insert(root, 13);
		root = insert(root, 7);
		
		System.out.print("Inorder Traversal of " +
						"the given tree is: ");
		inorderTraversal(root);
		
		root = removeOutsideRange(root, -10, 13);
		
		System.out.print("\nInorder traversal of " +
						"the modified tree: ");
		inorderTraversal(root);
	}
}


class __nod
{
	int ky;
	__nod Lft;
	__nod Rt;
}

Output:

Example 4)

<script>
//writing a Javascript program that will help us eliminate the keys which are out of the league. 
class __nod {
	constructor() {
		this.ky = 0;
		this.Lft = NILL;
		this.Rt = NILL;
	}
}
//we are now creating a binary search tree node consisting of key left and right pointers. 
// terminate all the nodes that have the data belonging to the outside range, and then it will automatically return the value of the root to the new tree. 
	function removeOutsideRange(root , min , max) {
		// BASE CASE
		if (root == NILL) {
			return NILL;
		}
// the first thing we have to do is to fix the left and right subtrees of the root of the binary search tree. 
		root.Lft =
		removeOutsideRange(root.Lft, min, max);
		root.Rt =
		removeOutsideRange(root.Rt, min, max);
// when we come back to fix the root, there will be two options: -
The first one will be that the key of the root is much smaller than the minimum value, and it is also not present in that particular range.
		if (root.ky < min) {
	var rchild = root.Rt;
			root = NILL;
			return rchild;
		}
// The second option that we have is that the root's key is much more significant than the maximum value present and is also not present in the range. 
		if (root.ky > max) {
	var lchild = root.Lft;
			root = NILL;
			return lchild;
		}
// the root is now present in the range.
		return root;
	}


	function new__nod(num) {
var temp = new __nod();
		temp.ky = num;
		temp.Lft = NILL;
		temp.Rt = NILL;
		return temp;
	}


	function insert(root , ky) {
		if (root == NILL) {
			return new__nod(ky);
		}
		if (root.ky > ky) {
			root.Lft = insert(root.Lft, ky);
		} else {
			root.Rt = insert(root.Rt, ky);
		}
		return root;
	}


	function inorderTraversal(root) {
		if (root != NILL) {
			inorderTraversal(root.Lft);
			document.write(root.ky + " ");
			inorderTraversal(root.Rt);
		}
	}
//writing the main code.	
var root = NILL;
		root = insert(root, 6);
		root = insert(root, -13);
		root = insert(root, 14);
		root = insert(root, -8);
		root = insert(root, 15);
		root = insert(root, 13);
		root = insert(root, 7);


		document.write("Inorder Traversal of " +
		"the given tree is: ");
		inorderTraversal(root);


		root = removeOutsideRange(root, -10, 13);


		document.write("<br/>Inorder traversal of " +
		"the modified tree: ");
		inorderTraversal(root);
</script>

Output:

Example 5)

#writing a Python program that will help us eliminate the keys which are out of the league. 
#we are now creating a binary search tree node consisting of key and left and right pointers. 
class new__nod:


	# we are creating a new node.
	def __init__(self, data):
		self.ky = data
		self.Lft = None
		self.Rt = None
		
# terminate all the nodes that have the data belonging to the outside range, and then it will automatically return the value of the root to the new tree. 
def removeOutsideRange(root, Min, Max):
	
	# Base Case
	if root == None:
		return None
	
	# the first thing we have to do is to fix the left and right subtrees of the root of the binary search tree. 
	root.Lft = removeOutsideRange(root.Lft, Min, Max)
	root.Rt = removeOutsideRange(root.Rt, Min, Max)
	
	# when we come back to fix the root, there will be two options: -
# The first one will be that the key of the root is much smaller than the minimum value, and it is also not present in that particular range.
	if root.ky < Min:
		rChild = root.Rt
		return rChild
		
	# The second option that we have is that the root's key is much larger than the maximum value present and is also not present in the range. 
	if root.ky > Max:
		lChild = root.Lft
		return lChild
		
	# the root is now present in the range.
	return root




# We have to create a utility function to help build a new binary search tree. 
def insert(root, ky):
	if root == None:
		return new__nod(ky)
	if root.ky > ky:
		root.Lft = insert(root.Lft, ky)
	else:
		root.Rt = insert(root.Rt, ky)
	return root


# we are now building another UF to help us insert a given key into the binary search tree. 
# creating a new function that will help us explore and visit the BST after the conversion. 
def inorderTraversal(root):
	if root:
		inorderTraversal( root.Lft)
		print(root.ky, end = " ")
		inorderTraversal( root.Rt)


# writing the main code.
if __name__ == '__main__':
	root = None
	root = insert(root, 6)
	root = insert(root, -13)
	root = insert(root, 14)
	root = insert(root, -8)
	root = insert(root, 15)
	root = insert(root, 13)
	root = insert(root, 7)


	print("Inorder traversal of the given tree is:",
										end = " ")
	inorderTraversal(root)


	root = removeOutsideRange(root, -10, 13)
	print()
	print("Inorder traversal of the modified tree is:",
											end = " ")
	inorderTraversal(root)

Output: