CareerCup

This is similar to checking whether tree is a BST or not, using min and max.
If root is in range keep root and run function on childs.
If root <min make right child as root and run function on it, free root and its left.
else make left child as root and run function on it, free root and its right part

BST * TrimTree(BST * root,int min, int max){
  if(!root) return NULL;
  
  if(root->data>=min && root->data<=max){
    root->left=TrimTree(root->left,min,root->data);
    root->right=TrimTree(root->right,root->data+1,max);
    return root;
  }
  if(root->data <min){
    BST * curRoot = root->right;
    root->right=NULL;
    freeNode(root); //frees root and all its childs
    return TrimTree(curRoot,min,max);
  }
  BST * curRoot = root->left;
  root->left=NULL;
  freeNode(root); //frees root and all its childs
  return TrimTree(curRoot,min,max);
}

Node Trim(Node root, int A, int B) {
   if(root==null) return null;
   
   if(root.data>B) return Trim(root.left,A,B);
   else if(root.data<A) return Trim(root.right,A,B);
   else {
       root.left=Trim(root.left,A,B);
       root.right=Trim(root.right,A,B);
   } 
   return root;
}

Do depth-first traversal, check value in each node and then call remove on that node if it's between A and B?

Or, we could go through each node, insert it into a new tree if value is between A and B

solutions above are not correct - in a BST if a node is within a range (A,B) it's not guaranteed that the parent of that node falls into that range as well. So just removing child nodes won't work.

Do the inorder traversal and delete what out of the range from the tree at the same time?

static void Trim(Tree<int> root, int m, int n)
        {
            if (root == null)
                return;

            if (root.Left != null && root.Left.Value < m)
            {
                root.Left = root.Left.Right;
            }
            Trim(root.Left, m, n);
            if (root.Right != null && root.Right.Value > n)
            {
                root.Right = root.Right.Left;
            }
            Trim(root.Right, m, n);

        }

{{

class Tree:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right

def preord(self):
print(self.data)
if self.left != None:
self.left.preord()
if self.right != None:
self.right.preord()

def inord(self):
if self.left != None:
self.left.inord()
print(self.data)
if self.right != None:
self.right.inord()

def postord(self):
if self.left != None:
self.left.postord()
if self.right != None:
self.right.postord()
print(self.data)

class BinaryTree(Tree):
def add(self, data):
if self.data == None:
self.data = data
return
if data<=self.data:
if self.left == None:
self.left = BinaryTree(data)
else:
self.left.add(data)
else:
if self.right == None:
self.right = BinaryTree(data)
else:
self.right.add(data)

def delete(self, data):
if self.data==data:
if self.left == None:
self.data = self.right.data
self.left = self.right.left
self.right = self.right.right
return
if self.right == None:
self.data = self.left.data
self.left = self.left.left
self.right = self.left.right
return
p1 = self.left
p2 = p1.right
while p2 != None and p2.right != None:
p1 = p2.right
self.data = p2.data
p1.right = None
return
if data<=self.data:
self.left.delete(data)
else:
self.right.delete(data)


class TrimBinaryTree(BinaryTree):
def add(self, data):
if self.data == None:
self.data = data
return
if data<=self.data:
if self.left == None:
self.left = TrimBinaryTree(data)
else:
self.left.add(data)
else:
if self.right == None:
self.right = TrimBinaryTree(data)
else:
self.right.add(data)

def trim(self, min, max):
if self.left != None:
if self.left.data < min:
self.left = None
else:
self.left.trim(min, max)
if self.right != None:
if self.right.data>max:
self.right = None
else:
self.right.trim(min, max)

#Tree(10, Tree('a'), Tree('cucu')).postord()
x = TrimBinaryTree()
x.add(20)
x.add(5)
x.add(3)
x.add(2)
x.add(4)
x.add(7)
x.add(9)
x.add(30)
x.add(25)
x.add(35)
x.add(11)
x.trim(11, 30)
x.inord()
}}

One can use Inorder traversal together with tree-delete which deletes the node. both this also are well known. so the code is:

Tree_trim(node *n)
{
if (!n)
return;
Tree_trim(n->left);
if(node->value < 'A || node->value > 'Z')
Tree_delete(node);
Tree_trim(n->right);
}

node* TrimTree(node* T,int A,int B)
   {
       if( null==T )return;
       if( A > B ) return TrimTree( T ,B , A );
       
       if( T->info < B || T->info > A )
         { Trim(T);return null }
       
       else
         {
             T->left = TrimTree(T->left);
             T->right = TrimTree(T->right);
         }

      return T ;    
       
   }

Write a Trim routine which takes care of memory freeing .

Assume A < B
Standard error checks assumed. Here's pseudo code

Case 1:
if A <= lowest(BST) && B >= highest(BST)
then
	return treeRoot

Case 2:
if A > highest(BST) || B < lowest(BST)
then
	return null

Case 3:
if A == highest(BST)
then
	unlink A from parent
	delete_tree(treeRoot)
	return A

Case 4:
if B == lowest(BST)
then
	unlink B from parent
	delete_tree(treeRoot)
	return B

/* all corner cases addressed above */

Case 5:
Set nodeA -> lowest(BST).
TestA:
if successor(nodeA) > A 
then
    nodeA is A.
else
     nodeA -> successor(nodeA)
     goto TestA
/* trim tree for nodeA */
delete_left_subtree(nodeA)
if nodeA is right_child
then
	great_ancestorA -> ancestor(nodeA) > A
	unlink_from_parent(nodeA)
	delete_left_subtree(great_ancestorA)
	left_child(great_ancestorA) -> nodeA
	
Set nodeB -> highest(BST)
TestB:
if predecessor(nodeB) < B
then
    nodeB is B
else
    nodeB -> predecessor(nodeB)
    goto TestB
/* trim tree for nodeB */
delete_right_subtree(nodeB)
if nodeB is left_child
then
	lower_ancestorB -> ancestor(nodeB) < B
	unlink_from_parent(nodeB)
	delete_right_subtree(lower_ancestorB)
	right_child(lower_ancestorB) -> nodeB
/* check ancestry relationship between nodeA and nodeB */
if nodeA is ancestor(nodeB)
then
    unlink_from_parent(nodeA)
	delete_tree(treeRoot)
	return nodeA

if nodeB is ancestor(nodeA)
then
	unlink_from_parent(nodeB)
	delete_tree(treeRoot)
	return nodeB

return treeRoot

post order traversal would work

public static TreeNode PostRecTrimT(TreeNode node,int a,int b)
	{
		if(node==null)
			return null;
		
			if(node.val>b && node.left!=null)
			{
				node=PostRecTrimT(node.left,a,b);
			}
			
		if(node.left!=null)
			{
				node.left=PostRecTrimT(node.left,a,b);
			}
		if(node.right!=null)
			{
				node.right=PostRecTrimT(node.right,a,b);
			}
		
		if(!(node.val<=b && node.val>=a))
			{
				
		//node.markedfordeletion but the right node has to be retained;
		if(node.right!=null && (node.right.val<=b && node.right.val>=a))
			{					
			     node=node.right;
			}//node.markedfordeletion but the left node has to be retained
		else if(node.left!=null && (node.right.val<=b && node.right.val>=a))
				{					
					node=node.left;
				}else//delete the node
				{
					node=null;
					
				}
				
				
				
			}

			
				
				
		return node;
	}

Here I am just using the inorder traversal and blocking any values outside the range using a simple if condition.
r1 - Lower Bound
r2 - Upper Bound

int BST::range(node* root,int r1,int r2) {
	if(root == NULL) {
		return 0;
	}
	
		if(root->left) { range(root->left,r1,r2); }
			if(root->data > r1 && root->data < r2) {
				cout<<root->data<<" ";
			}
		if(root->right) { range(root->right,r1,r2); }
	
}

I have a doubt regarding trimming of BST.
the new trimmed tree should contain the node which are in the range of int A and B.
if the code is 50 and you A and B is 10 and 30... so we will not consider this node as it is not in the range of A and B.

One example is required

static BinaryNode trimTheTree(BinaryNode root,int min,int max){
		if(root == null) return null;
		
		if(root.value >= min && root.value <= max){
			root.left = trimTheTree(root.left, min, max);
			root.right = trimTheTree(root.right, min, max);
		}else{
			while(root != null && (root.value < min || root.value > max)){
				if(root.value < min)
					root = root.right;
				else
					root = root.left;
			}
		}
		return root;
		
	}

with not cleaning the memory 
it's java :)

node* trim_bst(node* root, int min, int max)
{

    if(!root) {
        return NULL;
    }

    if ( !root->left && !root->right) {
        if (root->data < min || root->data > max) {        
            free(root);
            return NULL;
        } else
              return root;
    }

    if (min <= root->data  && root->data <= max) {

        root->left = trim_bst(root->left, min, max);
        root->right = trim_bst(root->right, min, max);

        return root;
    }

    if (max < root->data) {
             
        trim_bst(root->right, min, max);
        node* new_root = trim_bst(root->left, min,max);

        if (root!= new_root) {
            free(root);
        }

        return new_root;
    }

    if (root->data < min) {

        trim_bst(root->left, min,max);
        node* new_root = trim_bst(root->right, min, max);

        if (root!= new_root) {
            free(root);
        }

        return new_root;
    }

    return root;
}

void DeleteTree(struct node *root);

struct node * TrimTree(struct node **root, int min, int max)
{
	struct node *temp;
	
	if((*root) == NULL) return NULL;
	
	if(((*root)->value >= min) && ((*root)->value <= max))
	{
		((*root)->leftTree) = TrimTree(&((*root)->leftTree), min, max);
		((*root)->rightTree) = TrimTree(&((*root)->rightTree), min, max);
		return *root;
	}
	
	if((*root)->value < min)
	{
		DeleteTree((*root)->leftTree);
		temp = TrimTree(&((*root)->rightTree), min, max);		
	}
	else
	{
		DeleteTree((*root)->rightTree);
		temp = TrimTree(&((*root)->leftTree), min, max);		
	}	
	
	delete *root;
	*root = temp;
	return *root;
}


// Delete nodes in post order tree traversal
void DeleteTree(struct node *root)
{
	if(root != NULL)
	{
		DeleteTree(root->leftTree);
		DeleteTree(root->rightTree);
		delete root;
	}
}

#include<conio.h>
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node*left;
struct node*right;
};


void insert(struct node**q,int num)
{
struct node *temp=NULL;
temp=(struct node*)malloc(sizeof(struct node));
if(*q==NULL)
{
temp->data=num;
temp->left=NULL;
temp->right=NULL;
*q=temp;
// printf("%d\n",temp->data);
}
else
{
if(((*q)->data)>num)
insert(&((*q)->left),num);
else
insert(&((*q)->right),num);
}
}

void trim(struct node**p,int m,int n)
{
struct node*temp=*p;
if(*p==NULL)
return;
else
{
if(m>(*p)->data)
{
*p=(*p)->right;
temp->left=NULL;
temp->right=NULL;
free(temp);
trim(p,m,n);
}
else
{
if(n<(*p)->data)
{
*p=(*p)->left;
temp->left=NULL;
temp->right=NULL;
free(temp);
trim(p,m,n);;
}
else
{
trim(&(*p)->left,m,(*p)->data);
trim(&(*p)->right,(*p)->data,n);
}
}
}
}
void inorder(struct node*z)
{
if(z!=NULL)
{
inorder(z->left);
printf("%d\t",z->data);
inorder(z->right);
}
else return;
}
int main()
{
struct node*p;
p=NULL;

insert(&p,17);
insert(&p,13);
insert(&p,21);
insert(&p,27);
insert(&p,19);
insert(&p,8);
insert(&p,15);
trim(&p,20,25);
inorder(p);
getch();
return 0;
}

struct node* trim(struct node* root,int A,int B)
{
        struct node* temp;
        if(root)
        {
                if(root->data>=A && root->data<=B)
                {
                        root->left=trim(root->left,A,B);
                        root->right=trim(root->right,A,B);
                        return root;
                }
                else if(root->data<A)
                {
                        temp=root->right;
                        free(root);
                        return trim(temp,A,B);
                }
                else if(root->data>B)
                {
                        temp=root->left;
                        free(root);
                        return trim(temp,A,B);
                }
        }
        else
                return NULL;
}

Complete code here: ideone.com/xHclt

struct node* trim(struct node* root,int A,int B)
{
        struct node* temp;
        if(root)
        {
                if(root->data>=A && root->data<=B)
                {
                        root->left=trim(root->left,A,B);
                        root->right=trim(root->right,A,B);
                        return root;
                }
                else if(root->data<A)
                {
                        temp=root->right;
                        free(root);
                        return trim(temp,A,B);
                }
                else if(root->data>B)
                {
                        temp=root->left;
                        free(root);
                        return trim(temp,A,B);
                }
        }
        else
                return NULL;
}

Complete code here: ideone.com/xHclt

Here's the complete code, this question is indeed similar to the one for checking if a tree is BST or not but the tricky part is avoiding memory leaks:

node trim (node root, int a, int b) {
	if(root == null)
		return null;
	if(root.data > a && root.data < b) {
		root.left = trim(root.left, a, b);
		root.right = trim(root.right, a, b);
		return root;
	} else if(root.data < a){
		node temp = root.right;
		freeTree(root.left);
		free(root)
		return trim(temp, a, b); 
	} else if(root.data > b) {
		node temp = root.left;
		freeTree(root.right);
		free(root);
		return trim(temp, a, b); 
	}
}

//postOrder traversal Deletion
void freeTree (node n) {
	if(n == null)
		return;
	freeTree(n.left);
	freeTree(n.right);
	free(n)
}

Seems easy...
I work in JAVA/C++ AS3 so syntax would be eaten up!!

function freeBST(BST *p)
{
if(p->left) freeBST(p->left);
if(p->right) freeBST(p->right);
free(p);
return null;
}


function searchBST(BST *p,int a)
{

while(p && p->val!=a)
 {
 if(p->val > a) p=p->left; else p=p->right;
 }

return p;
}


function trimBST(BST *p,int a, int b)
{
BST *aP= searchBST(p,a);
BST *bP= searchBST(p,b);



aP->left=freeBST(aP->left);
bP->right=freeBST(bP->right);

}

If we remove the assumption that both A or B are for sure present than all that is needed to be changed is to add a FindNearestElementBST in the code above

If we remove the assumption that both A or B are for sure present than all that is needed to be changed is to replace searchBST by a FindNearestElementBST in the code above

Yes Trim tree won't work, Make BST from this array 100 is root {100,80,10,5,11,90,85,95,120,110,108,115,150,145,170}, it resolves to a complete BST of height 4. Trim Tree for all values between 90 and 110 including 90 and 110 does not make sense. 80, and 120 will hang above 90 and 110. We can only return all values between two given numbers.
So Question is ambiguous.