## Code Avinya

Software Development Blogs

# Trim a binary search tree

So, in this problem “Trim a binary search tree”, we have given a root node of a binary search tree and the low and high values. According to the low and high values, we have to consider the nodes of an output binary tree.

- Next, we have to trim the tree so that all its elements lies between the low and high element.

- As an output, we have to return
*the root node and other nodes’ values of the trimmed binary search tree*.

## How to trim a binary search tree?

Before going to the code, we have to consider some conditions like:

- We have to check, if the root value is less than the low value, then the answer will be in the root node right subtree.
- Next, we will check, if the root node is greater than the high value. If this is the case, then the trim node will be in the root node left subtree.
- Finally, when the root node is in range, the trimmed tree will contain the root node and the root node left child contains the left tree result and the root node right child contains the right tree result. And we will repeat the same recursively call for both left and right tree results.

## What is the concept of Trimming a binary search tree?

Trimming a binary search tree is a method where we remove nodes from the binary tree that are not falling within our mentioned range.

While trim the binary search tree, we have to specify the range lower and higher. Then, we will modify the tree such that all node values which are less than “l” or greater than “r” should be removed from a binary tree.

## Code:

#include <iostream> struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) { val=x; left=NULL; right=NULL; } }; TreeNode* trimBST(TreeNode* root, int l, int r) { if (!root) return NULL; if (root->val < l) return trimBST(root->right, l, r); if (root->val > r) return trimBST(root->left, l, r); root->left = trimBST(root->left, l, r); root->right = trimBST(root->right, l, r); return root; } void inOrderTraversal(TreeNode* root) { if (root) { inOrderTraversal(root->left); std::cout << root->val << " "; inOrderTraversal(root->right); } } int main() { TreeNode* root = new TreeNode(1); root->left = new TreeNode(0); root->right = new TreeNode(2); int l = 1; int r = 2; root = trimBST(root, l, r); inOrderTraversal(root); return 0; }

## Explanation of the above code:

1. We will start traversing the tree from the root node.

2. At each node, we will compare that node value to the range [l, r]. If the binary tree node’s value is outside the range, that node needs to be removed for a new binary tree, along with its entire subtree.

3. Next, we will recursively trim the left and right subtrees based on whether the node’s value is less than `l` or greater than `r` or not.

4. And if the node’s value of the binary tree falls within the range [l, r], it is a valid node that should be kept in the newly trimmed tree.

5. For the above case, the root node remains as is, and the trimming process continues for its left and right subtrees as mentioned above.

6. After trimming all the necessary nodes, return the modified subtree by each recursive call.

## Why do we need the concept of Trimming a binary search tree?

Triming a binary search tree is an essential function when we just want to focus on a specific subset within the binary tree while still maintaining the binary search tree’s ordered structure.

## Summary

Trimming a binary search tree allows us to optimize our data representation and make it more tailored to the specific requirements of our application. It also ensures that our binary search tree remains relevant, efficient, and effective in certain situations.

### About Us

Myself Bharath Choudhary, software developer at Oracle.

2021 NIT Warangal graduate.

### Categories

- About Companies (21)
- System Design (6)
- Uncategorized (36)

### Quick Contact

contact@codeavinya.com

Saturday – Sunday

10 AM – 5 PM

Follow Us :