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

Why is Binary Heap Preferred over BST for Priority Queue

A priority queue is a linear and ordered collection of elements in which each element has an attribute named priority and the priority attribute decides the order in which elements...

2 minutes read.

What is a 2-3 Tree in Data Structure?

Tree Data structure The information about the tree is self-explanatory. Trees are ordered and, therefore, not linear. But they are actually designed differently. Tree A node-based data model that represents and...

5 minutes read.

Strings in Data Structures

Strings and functions in C A string is a collection of characters. We'll learn how to declare strings, operate with strings in C programming, and use pre-defined string handling routines. We'll look...

7 minutes read.

What is the B+ Tree in Data Structures?

We all know that the B+ tree in data structures is nothing but just an extended version of the B tree. It allows the smooth working of all the operations...

7 minutes read.

Buffer overflow attack with examples

You have undoubtedly faced the term buffer overflow in your programming journey. Many times it occurs when we try to run a piece of code with user input, but it...

4 minutes read.

Sorting Algorithms in Data Structures

A sorting algorithm is used to organize the elements of an array or list. Sorting an array, for example. Unsorted array 572941 Sorted array 124579 We're sorting the array in ascending order right now. This procedure...

4 minutes read.

Types of Data Structures

Almost every programme or software system that has been built makes use of data structures. Furthermore, data structures are basics of computer science and software engineering. When it comes to...

7 minutes read.

Given a Binary Tree, Check if it's balanced

Implementation /*Creating a C++ program that will help us identify whether the given tree is height-balanced or not.  */ #include <bits/stdc++.h> using namespace std; /* A particular binary tree node consists of data with some...

4 minutes read.

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.

Post-order traversal in a binary tree

We all know that postorder is a form of tree traversal to visit the tree's nodes, and it helps us reach out to the tree's nodes. Postorder means visiting the...

4 minutes read.

Data Structure Infix to Postfix Conversion

Infix to Postfix Conversion The infix expression is easy to read and write by humans. In present time, we use the infix expression in our daily life but the computers are...

4 minutes read.

Delete a Node without head pointer from the linked list

Delete a Node without head pointer from the linked list This article will explain how to delete a node without a head pointer from the linked list. We have given a...

2 minutes read.

Linear Search

Searching: In the data structure, searching is the process in which an element is searched in a list that satisfies one or more than one condition. Types of searching There are two...

4 minutes read.

Deletion in Binary Search Tree

Implementation #include <iostream> using namespace std; struct _nod {   int ky;   struct _nod *Lft, *Rt; }; // Creating a node in the binary tree. struct _nod *nw_nod(int Itm) {   struct _nod *temp = (struct _nod *)malloc(sizeof(struct...

4 minutes read.

Recaman’s Sequence

Recamán's succession repeat connection in arithmetic and software engineering. Since its components are obviously connected with the past components, they are as often as possible characterized utilizing recursion. It takes its...

4 minutes read.

Properties of Binary Tree

Trees are maybe of the most significant datum structures. They are used to store and figure out data. A binarytree is a tree data structure made from nodes, all of which has...

3 minutes read.

AVL Tree

AVL Tree AVL Tree is referred to as self-balanced or height-balanced binary search tree where the difference between heights of its left subtree and right subtree (Balance Factor) can't more than...

25 minutes read.

Introduction to 2D-Arrays

Two Dimensional Array Technical Definitions An array of arrays is a common definition for a two-dimensional array. A matrix is another name for a two-dimensional array. A matrix looks like a table...

3 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.

Semi-Structured data

In this article, we will discuss the semi-structured data. Data can be defined as the distinct piece of information that is gathered and translated for some purpose. It can be...

5 minutes read.