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 <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {
11 if (!root) return NULL;
12 if (root->val < low) return trimBST(root->right, low, high);
13 if (root->val > high) return trimBST(root->left, low, high);
14 root->left = trimBST(root->left, low, high);
15 root->right = trimBST(root->right, low, high);
16 return root;
17}The recursive function trimBST checks if the node is NULL. If the node's value is less than low, it trims the left subtree. If the node's value is greater than high, it trims the right subtree. Otherwise, it recursively processes both 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;
4
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.