Logo
×

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:

Trim a binary search tree

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:

Trim a binary search tree

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:

Trim a binary search tree

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:

Trim a binary search tree

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:

Trim a binary search tree

Related Topics

Intersection Point in Y Shaped Linked Lists in Java

Intersection Point in Y Shaped Linked Lists in Java In this article, we are going to see how to find the intersection point in a Y-shaped linked list. Method 1: We need to...

4 minutes read.

Convert a Binary Tree into a Binary Search Tree

Implementation #include <stdio.h>   #include <stdlib.h>       //creating a node of the binary tree.  struct __nod{       int record;       struct __nod *Lft;       struct __nod *Rt;   };       // presenting the root of the binary tree.   struct...

5 minutes read.

Linear Queue VS Circular Queue

What is Queue? A queue is one of the important linear data structures extensively used in various computer applications. It is based on the FIFO (First In First Out) principle. It...

9 minutes read.

Circular Queue

Circular Queue Circular Queue is special type queue, which follows First in First Out (FIFO) rule and as well as instead of ending queue at the last position, it starts again...

4 minutes read.

What Is Dfs Algorithm in Data Structures

DFS stands for Depth First Search. Generally, it is a repetitive or decidable type of algorithm which is basically used in identifying all the vertices or nodes of a graph...

5 minutes read.

Finding Rank in a Binary Search Tree

Implementation // writing a C++ program to find out the rank and element in the program.  #include <bits/stdc++.h> using namespace std; struct __nod { int record; __nod *Lft, *Rt; int LftSize; }; __nod* new__nod(int record) { __nod *temp = new __nod; temp->record...

6 minutes read.

Lowest Common Ancestor in a Binary Tree

The lowest node in the tree that contains both n1 and n2 as descendants is the lowest common ancestor (LCA), and n1 and n2 are the nodes for which we...

11 minutes read.

Sort the linked list of 0s, 1s and 2s

Sort the linked list of 0s, 1s and 2s In this, we are given a linked list of 0s, 1s, and 2s, and we need to sort it. Examples: Input: 1  ->  1 ...

2 minutes read.

Equal Sum

Find an element in array such that the sum of left array is equal to the sum of right array You have been given an array of numbers. You have to...

4 minutes read.

Horizontal and Vertical Scaling

Being a software engineer, you would have designed a website or application and deployed it on any server. Imagine that the developed application starts getting popular, and many users engage...

6 minutes read.

Berkley’s Algorithm

Berkley’s Algorithm is mainly used in clock synchronization system. It is used in distributed systems. To implement this algorithm, we have to think that the network has no accurate time...

4 minutes read.

CSS Text-indent

Text-indent The Text-indent property of CSS is used to set any first line’s indentation inside a text’s block. It describes the horizontal space amount that puts establish before the text line. It...

3 minutes read.

Stack Data Structure

The stack is a non-primitive and linear data structure. It works on the principle of LIFO (Last In First Out). That is, the element that is added to the end...

3 minutes read.

Sum of Nodes in a Binary Tree

In this article, we will see the sample problems that will help us understand the concept and summation of all the nodes in the binary tree. Implementation /* creating a program that...

4 minutes read.

Advantages and Disadvantages of Linked List

Advantages of Linked List The linked list is a dynamic data structure.You can also decrease and increase the linked list at run-time. That is, you can allocate and deallocate memory at...

3 minutes read.

Remove duplicates from an unsorted Linked List

Remove duplicates from an unsorted Linked List This article will explain how we can remove duplicates from unsorted linked lists. Here we have given an unsorted singly linked list and will...

3 minutes read.

Bubble sort algorithm using Javascript

Sorting is a very useful technique in many algorithms and programs. Basically, sorting operations help us to arrange a set of data in a particular manner. Bubble sort is one...

3 minutes read.

Shell Sort

Shell Sort: Shell sort is a sorting algorithm. It is an extended version of the insertion sort. In this sorting, we compare the elements that are distant apart rather than the...

5 minutes read.

Box Stacking Problem

Stacking of boxes depending on their base You have been given n different boxes. These boxes will have different heights, widths, and depths. You have to stack all these boxes in...

4 minutes read.

Data Structure Infix to Prefix Conversion

Infix to Prefix Conversion In present time, we use the infix expression in our daily life but the computers are not able to understand this format because they need to keep...

4 minutes read.