Trim a Binary Search Tree

Problem Statement: Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant).
Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1:

Input: root = [5,1,6,0,2,null,7], low = 5, high = 10
Output: [5,null,6,null,7]

Approach:

A simple DFS approach can be used to solve this problem. As we don't need to include those nodes whose value is out of the given range i.e low and high. When we get node.data < low, we know that trimmed Binary tree must lie to the right of node and when we get node.data > high, it means trimmed binary tree must occur to the left of node.

Code Implementation:

Java

import java.util.LinkedList;
import java.util.Queue;

public class TrimBST {

    static class Node {
        int data;
        Node left, right;

        // Constructor
        Node(int key) {
            data = key;
            left = right = null;
        }
    }

    public static void main(String[] ans) {
        /*
         * Creating Binary Search Tree The created BST is same as in the above given
         * figure (refer figure for reference)
         */
        Node root = new Node(5);
        root.left = new Node(1);
        root.right = new Node(6);
        root.left.left = new Node(0);
        root.left.right = new Node(2);
        root.right.right = new Node(7);

        /* defining range */
        int low = 5;
        int high = 10;

        /* calling method */
        trimBST(root, low, high);

        /* printing the answer */
        levelOrder(root);
    }

    /* method to trim the BST */
    private static Node trimBST(Node root, int low, int high) {
        if (root == null)
            return null;

        /*
         * If current root value is less than low so we will discard the left subtree of
         * current root
         * and trimmed bst must occur to the right
         */
        if (root.data < low) {
            return trimBST(root.right, low, high);
        }
        /*
         * If current root value is greater than high so we will discard the right
         * subtree of current root
         * and trimmed bst must occur to left
         */

        else if (root.data > high) {
            return trimBST(root.left, low, high);
        }

        /*
         * if these conditions fail then we are sure that it is between left and right
         * side of tree so trim both.
         */
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;
    }

    /* printing the trimmed tree */
    private static void levelOrder(Node root) {
        if (root == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {

            Node tempNode = queue.poll();
            System.out.print(tempNode.data + " ");

            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }
    }
}

Output:

5 6 7

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in tree.

Space Complexity:O(n), as we are using recursion hence extra stack space is used which can go upto number of nodes (n).

If you want to contribute such articles to solutions2coding.com please click here. Thank you!