Write a function named range
that removes from a binary tree any elements that are not in a given range, inclusive.
Your function accepts three parameters: a reference to a pointer to a BinaryTreeNode
representing the root of a tree, and a minimum and maximum integer.
You should remove from the tree any elements whose values are not in the range of [min .. max], inclusive.
You should also return an integer count of the number of elements that were removed, if any.
For this function, assume that your tree is a binary search tree (BST) and that its elements are arranged in a valid BST order.
Your function should maintain the BST ordering property of the tree.
For example, suppose a variable named tree
points to the root of a tree that stores the following elements:
(50 (38 (14 (8) (20 / (26))) (42)) (90 (54 / (72 (61) (83)))))
The table below shows what the state of the tree would be if various calls were made.
The calls shown are separate; it's not a chain of calls in a row.
Also notice that each call returns the number of nodes that were removed.
range(tree, 25, 72) 
range(tree, 54, 80) 
range(tree, 18, 42) 
range(tree, 3, 6) 
(50 (38 (26) (42)) (54 / (72 (61))))

(54 / (72 (61)))

(38 (20 / (26)) (42))

(empty tree)

returns 5 
returns 9 
returns 8 
returns 12 
Do not leak memory; if you remove a node from the tree, free the memory associated with that node.
If the range is invalid (if the minimum exceeds the maximum), throw an integer exception and don't modify the tree.
Constraints:
You must implement your function recursively and without using loops.
Your solution should be at worst O(N) where N is the number of elements in the tree.
Do not construct any new BinaryTreeNode
objects in solving this problem (though you may create as many BinaryTreeNode*
pointer variables as you like).
Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).
You may define helper functions.
You should not modify the tree passed in as the parameter.
You also should not change the data
of any nodes.
Assume that you are using the BinaryTreeNode
structure as defined below:
struct BinaryTreeNode {
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
};