Binary trees are one of the most famous data structures in computer science. In binary trees, each node can have at most two children. In computing, binary trees are mainly used for searching and sorting as they provide a facility to store data hierarchically. Due to this and many other advantages of a binary tree, it is one of the commonly asked topics while cracking any technical interview. In this article, we discuss one such problem “Trim a binary search tree” with the concept of the binary tree which can help you get into your dream company.
What is Trim a Binary Search Tree Problem?
Given the root of the binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lie in [low, high].
Trimming the tree should not change the relative structure of the elements that will remain in the tree. It can be proven that there is a unique answer.
For Example:
L = 6 R = 8
Solutions to Trim a Binary Search Tree Problem
There are two approaches to solve this problem. Let us understand them in detail below:
Method 1: Recursive postorder traversal
The algorithm first performs a postorder traversal of the binary tree, then recursively descends the left and right subtrees in the range [L, R] of the given tree root using the function TrimBST(), after which the root node is processed.
- If the root node is greater than R, then return the left child of the root
- Else if the root node has a value smaller than L, return the right child of the root
- Else if the root node value is between [L, R], then there’s no need to change the root
Running Process 1 or Process 2 will return a tree node whose value lies in the range [L, R] as we previously trimmed the left and right subtrees of the root node.
Algorithm
Define recursive function Return null if the tree is empty Trim left subtree recursively Trim right subtree recursively Consider root node: If the root node is between [L, R], return it as it is. Else if the root node value is smaller than L, return root.right Else if the root node value is greater than R, return root.left
C++ Code
#include #include <bits/stdc++.h> using namespace std; class treeNode { public: int data; treeNode *l; treeNode *r; treeNode(int num) { data = num; l = r = NULL; } }; treeNode *TrimBST(treeNode *root,int L,int R) { if (root == NULL) return root; root->l = TrimBST(root->l,L,R); root->r = TrimBST(root->r,L,R); if(root->data < L || root->data > R) { if(root->l == NULL) return root->r; if(root->r == NULL) return root->l; } return root; } static void inOrder(treeNode *root) { if(root == NULL) return; inOrder(root->l); cout<<root->data<<" "; inOrder(root->r); } int main() { treeNode *root = new treeNode(3); root->l = new treeNode(2); root->r = new treeNode(5); root->l->l = new treeNode(6); root->l->r = new treeNode(7); root->r->l = new treeNode(4); root->r->r = new treeNode(8); cout<<"Inorder traversal without trimming: "; inOrder(root); int L = 6; int R = 8; root = TrimBST(root,L,R); cout<<endl; cout<<"Inorder traversal with trimming: "; inOrder(root); return 0; }
Output
Inorder traversal without trimming: 6 2 7 3 4 5 8 Inorder traversal with trimming: 6 2 7 3 8
Java Code
import java.io.*; import java.util.*; class TutorialCup { static class treeNode { int data; treeNode l; treeNode r; treeNode(int num) { data = num; l = r = null; } } static treeNode TrimBST(treeNode root,int L,int R) { if (root == null) return root; root.l = TrimBST(root.l,L,R); root.r = TrimBST(root.r,L,R); if(root.data < L || root.data > R) { if(root.l == null) return root.r; if(root.r == null) return root.l; } return root; } static void inOrder(treeNode root) { if(root == null) return; inOrder(root.l); System.out.print(root.data+" "); inOrder(root.r); } public static void main (String[] args) { treeNode root = new treeNode(3); root.l = new treeNode(2); root.r = new treeNode(5); root.l.l = new treeNode(6); root.l.r = new treeNode(7); root.r.l = new treeNode(4); root.r.r = new treeNode(8); System.out.print("Inorder traversal without trimming: "); inOrder(root); int L = 6; int R = 8; root = TrimBST(root,L,R); System.out.println(); System.out.print("Inorder traversal with trimming: "); inOrder(root); } }
Output
Inorder traversal without trimming: 6 2 7 3 4 5 8 Inorder traversal with trimming: 6 2 7 3 8
Time Complexity
The time complexity of the above approach is O(n) where n is the number of nodes in BST. Also, the space complexity of the approach is O(1) as it does not require any extra space to solve the problem.
Method 2: Iterative preorder traversal
The goal of the algorithm is to convert the iterative preorder traversal into a recursive version by using the stack data structure and later, the root node is processed before its children. However, this approach is not optimal to use as it requires extra space to store the elements in the stack data structure. The algorithm was explained below.
Algorithm
Define a function findRoot() that takes the tree's root node and performs the following: If the node value is in the range [L, R], return the node. If the root node’s value is less than L, examine the right subtree to find the nearest in-order predecessor of the root whose value is between L and R. If the root node value is greater than L, look for the nearest inorder predecessor of the root node (in the left subtree) that has a value in the range [L, R] and return that node. The root node of the trimmed BST returned by findRoot() is the new root. A stack is a data structure that facilitates the reverse traversal of a DFS tree. Push the new node onto the stack and begin traversal. When a node is traversed, pop it off the stack and push its left and right children (if present) onto the stack. If a node has left children whose value is less than L, find the inorder successor of these subnodes, and assign them as the left children of the popped node. If the popped node has the right children with values greater than R, find the first node in the in-order predecessor list of these children and assign it as the right child of the popped node. Return the root node after the traversal is finished.
Time Complexity
The time complexity of the above approach is O(n) where n is the number of nodes in the BST. Moreover, the space complexity of the above approach is O(n) as the approach uses the stack space to solve the problem.
Conclusion
A binary tree is a hierarchical structure that contains nodes with a left and a right child, as well as a value for each node. In this article, we studied how you can trim a binary search tree using various approaches and their respective codes. It is recommended to learn such competitive problems to get into your dream company and if you face any difficulty, do not worry, our live coding help tutors are always ready to help you!
