Trim a Binary Search Tree - Recursive vs Iterative Solutions

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