CodeStepByStep

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.

(50 (38 (26) (42)) (54 / (72 (61))))

(54 / (72 (61)))

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

(empty tree)

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;
};