Remove BST keys outside the given range in c#

Remove BST keys outside of given range

Csharp program for Remove BST keys outside the given range. Here mentioned other language solution.

// Include namespace system
using System;
// Csharp program for
// Remove BST keys outside the given range
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public BinarySearchTree()
	{
		this.root = null;
	}
	// Insert a node element
	public void addNode(int data)
	{
		// Create a new node
		var node = new TreeNode(data);
		if (this.root == null)
		{
			// When adds a x node in bst
			this.root = node;
		}
		else
		{
			var find = this.root;
			// Add new node to proper position
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						// When left child empty
						// So add new node here
						find.left = node;
						return;
					}
					else
					{
						// Otherwise
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						// When right child empty
						// So add new node here
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	public TreeNode removeOutsideXY(TreeNode node, int x, int y)
	{
		if (node != null)
		{
			node.left = this.removeOutsideXY(node.left, x, y);
			node.right = this.removeOutsideXY(node.right, x, y);
			if (node.data > y || node.data < x)
			{
				// Condition which are delete node
				if (node.left == null && node.right == null)
				{
					// delete leaf node
					return null;
				}
				else if (node.left == null)
				{
					return node.right;
				}
				else if (node.right == null)
				{
					return node.left;
				}
			}
		}
		return node;
	}
	public void removeOutsideRange(int x, int y)
	{
		if (this.root != null)
		{
			if (x > y)
			{
				Console.WriteLine("\n  Range of [" + y + " - " + x + "]");
				this.root = this.removeOutsideXY(this.root, y, x);
			}
			else
			{
				Console.WriteLine("\n  Range of [" + x + " - " + y + "]");
				this.root = this.removeOutsideXY(this.root, x, y);
			}
		}
		else
		{
			Console.WriteLine("Empty Tree");
		}
	}
	public void preorder(TreeNode node)
	{
		if (node != null)
		{
			Console.Write("  " + node.data);
			// Visit left sub-tree
			this.preorder(node.left);
			// Visit right sub-tree
			this.preorder(node.right);
		}
	}
	public static void Main(String[] args)
	{
		var tree = new BinarySearchTree();
		/*
		    Binary search tree
		    ------------------
		          6
		         /  \ 
		        /    \
		       /      \
		      3        9
		     /  \     / \
		    1    5   7   11
		   / \   /    \    \
		 -3  2  4      8    12

		*/
		tree.addNode(6);
		tree.addNode(3);
		tree.addNode(9);
		tree.addNode(1);
		tree.addNode(5);
		tree.addNode(7);
		tree.addNode(8);
		tree.addNode(11);
		tree.addNode(-3);
		tree.addNode(2);
		tree.addNode(12);
		tree.addNode(4);
		tree.preorder(tree.root);
		// Test
		// range (5..8)
		tree.removeOutsideRange(5, 8);
		/*
		    After remove
		    ------------------
		          6
		         / \ 
		        /   \
		       /     \
		      5       7
		               \
		                8             
		*/
		tree.preorder(tree.root);
	}
}

Output

  6  3  1  -3  2  5  4  9  7  8  11  12
  Range of [5 - 8]
  6  5  7  8



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







© 2022, kalkicode.com, All rights reserved