Sponsored
Sponsored
We can utilize the properties of a BST to perform a recursive traversal. The strategy here involves:
low, we need to trim the left subtree and consider the right subtree.high, we trim the right subtree and consider the left subtree.low, high], we recursively trim both subtrees.Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once.
Space Complexity: O(h), where h is the height of the tree, representing the recursion stack.
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11TreeNode* trimBST(TreeNode* root, int low, int high) {
12 if (!root) return NULL;
13 if (root->val < low) return trimBST(root->right, low, high);
14 if (root->val > high) return trimBST(root->left, low, high);
15 root->left = trimBST(root->left, low, high);
16 root->right = trimBST(root->right, low, high);
17 return root;
18}The function trimBST is similar to its C counterpart, using the BST properties to recursively adjust subtrees.
This iterative approach uses a stack to traverse the tree. The main idea is to mimic the recursive depth-first search using an explicit stack.
Time Complexity: O(n), as each node is processed once.
Space Complexity: O(h), where h is the height of the tree, due to the stack usage.
1#include <iostream>
2#include <stack>
3using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (!root) return NULL;
while (root && (root->val < low || root->val > high)) {
root = root->val < low ? root->right : root->left;
}
TreeNode* current = root;
stack<TreeNode*> nodeStack;
while (current || !nodeStack.empty()) {
while (current) {
if (current->val >= low && current->val <= high) {
nodeStack.push(current);
current = current->left;
} else {
current = current->val < low ? current->right : current->left;
}
}
if (!nodeStack.empty()) {
current = nodeStack.top()->right;
nodeStack.pop();
}
}
return root;
}Instead of using recursion, this C++ implementation uses a stack to perform depth-first search-like traversal. It adjusts the nodes based on their values compared to the bounds low and high, ensuring all nodes in the stack are within the bounds.