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.
1import java.util.Stack;
This Java example shows an iterative approach using a stack to maintain the modified tree's structure while keeping nodes within bounds. Each node is processed, ensuring valid nodes are stacked for later traversal.