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.
1class TreeNode:
2
The Python solution employs a stack for an iterative node traversal. Adjustments are made according to the node values relative to low and high. Nodes are appended to a stack for traversal if they are valid.