Problem Statement: Remove the values from the Binary search tree which are out of the given range
Ex: Input tree
Input Range: 10 to 16
Output Values: 10, 12, 13, 14, 16
Code:
class LocalTree2{
public int val;
public LocalTree2 leftTree;
public LocalTree2 rightTree;
static int MIN = 9;
static int MAX = 11;
static public LocalTree2 init;
public LocalTree2(int i) {
val = i;
}
public void add(int i){
LocalTree2 temp = this;
LocalTree2 parent = this;
while (temp != null){
parent = temp;
if ( i > temp.val){
temp = temp.rightTree;
}else{
temp = temp.leftTree;
}
}
temp = new LocalTree2(i);
if ( i > parent.val){
parent.rightTree = temp;
}else{
parent.leftTree = temp;
}
}
public LocalTree2 deleteFromTree(LocalTree2 tree, int value){
if (tree == null)
return tree;
if (tree.val < value){
tree.rightTree = deleteFromTree(tree.rightTree, value);
}else{
if (tree.val > value){
tree.leftTree = deleteFromTree(tree.leftTree, value);
}else{
LocalTree2 successorNode = getInOrderSucessor2(tree);
if (successorNode != null){
tree.val = successorNode.val;
tree.rightTree = deleteFromTree(tree.rightTree, tree.val);
}else{
tree = tree.leftTree;
}
}
}
return tree;
}
private int getInOrderSucessor(LocalTree2 node) {
if (node.rightTree != null){
node = node.rightTree;
}
while (node.leftTree != null ){
node = node.leftTree;
}
return node.val;
}
private LocalTree2 getInOrderSucessor2(LocalTree2 node) {
if (node == null || node.rightTree == null){
return null;
}
node = node.rightTree;
while (node.leftTree != null ){
node = node.leftTree;
}
return node;
}
public void printTree(LocalTree2 root){
if (root == null)
return;
printTree(root.leftTree);
System.out.println(root.val);
printTree(root.rightTree);
}
public LocalTree2 findNode(LocalTree2 root, int val){
if (root == null)
return null;
LocalTree2 node = findNode(root.leftTree, val);
if ( node != null)
return node;
if (root.val == val)
return root;
node = findNode(root.rightTree, val);
if ( node != null)
return node;
return null;
}
public LocalTree2 filterNode(LocalTree2 tree, int minFilter, int maxFilter){
if (tree == null)
return tree;
tree.leftTree = filterNode(tree.leftTree, minFilter, maxFilter);
while (tree != null && ((tree.val < minFilter) || (tree.val > maxFilter) )){
tree = deleteFromTree(tree, tree.val);
}
if (tree != null)
tree.rightTree = filterNode(tree.rightTree, minFilter, maxFilter);
return tree;
}
}
public class BST {
public static void main(String[] args) {
LocalTree2 l = new LocalTree2(8);
l.add(3);
l.add(1);
l.add(6);
l.add(4);
l.add(7);
l.add(10);
l.add(14);
l.add(13);
l.add(12);
l.add(16);
l.printTree(l);
l = l.filterNode(l, 10, 16);
System.out.println("************** Post Filtering ********************");
l.printTree(l);
}
}
