How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)?

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:
Input:

    1
   / \
  0   2

L = 1
R = 2

Output

: 
    1
      \
       2

Example 2:
Input:

    3
   / \
  0   4
   \
    2
   /
  1

L = 1
R = 3

Output:

      3
     / 
   2   
  /
 1

Depth First Search Algorithm to Trim a Binary Tree using Recursion

We can recursively solve the problem by identifying a few cases:

• If the node is null, the trimmed version will be null, obviously.
• If the node’s value is within the range of lower and upper bound [L, R], then its left and right sub trees should be trimmed recursively.
• If the node’s value falls outside the bounds [L, R], we can safely remove the node in the result tree by returnning the trimmed version of its left or right sub tree accordingly.

Recursion makes the algorithm easy to implement and be illustrated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (root == nullptr) return root;
        if (root->val > R) return trimBST(root->left, L, R);
        if (root->val < L) return trimBST(root->right, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (root == nullptr) return root;
        if (root->val > R) return trimBST(root->left, L, R);
        if (root->val < L) return trimBST(root->right, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};

The above C++ code implements the Depth First Search (DFS) Algorithm that trims a given binary tree (root pointer to the tree). The time complexity is O(N) because in worst cases every node is preserved in the trimed version of the binary tree. The space complexity is O(H) where H is the height of the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —