For most binary tree problems, recursive solutions are the most elegant and compact. LeetCode exercise Trim a Binary Search Tree is not an exception.

In a nutshell, the task is to remove all values higher than `high` and all values lower than `low` from a binary search tree. You can have a look at the full description here.

The recursive solutionâ€™s core idea is that if `current.val > high`, the result tree does not include the current node, and the nodes to trim are somewhere within the left subtree. Equally, when `current.val < low`, the right subtree contains the elements to trim. When the value is within `low` and `high`, we continue searching for nodes to trim in both subtrees.

``````public static TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return root;
if (root.val > high) return trimBST(root.left, low, high);
if (root.val < low) return trimBST(root.right, low, high);

root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
``````

If recursion is not your thing, there is an iterative alternative. One option is to divide the problem into two, handling the low and high trims separately. I use a dummy node in this implementation so that the root node is not a special case.

``````public static TreeNode trimBST(TreeNode root, int low, int high) {
return trimLow(trimHigh(root, high), low);
}

private static TreeNode trimHigh(TreeNode root, int high) {
TreeNode dummy = new TreeNode(Integer.MAX_VALUE, null, root);
TreeNode current = dummy;

while (current != null && current.right != null) {
if (current.right.val > high) {
current.right = current.right.left;
} else {
current = current.right;
}
}
return dummy.right;
}

private static TreeNode trimLow(TreeNode root, int low) {
TreeNode dummy = new TreeNode(Integer.MIN_VALUE, root, null);
TreeNode current = dummy;

while (current != null && current.left != null) {
if (current.left.val < low) {
current.left = current.left.right;
} else {
current = current.left;
}
}
return dummy.left;
}
``````