Return a pruned BST containing only nodes whose values are within an inclusive range.
Write a function `trim_bst(root, low, high)` that takes the root of a binary search tree (BST) and two integers `low` and `high` (with `low <= high`). Each node is represented as a dictionary with keys `'val'`, `'left'`, and `'right'` (where `'left'` and `'right'` are either dictionaries or `None`). The function should return the root of a new BST that contains only the nodes from the original tree whose values are in the inclusive range `[low, high]`. The resulting tree must still be a valid BST and preserve the original relative structure as much as possible. You may trim in place and return the modified original tree. If the original tree is empty, return `None`.
**Details:**
- All values in the left subtree of a node are less than the node's value, and all values in the right subtree are greater.
- All node values are distinct.
- The solution must run in `O(n)` time and `O(h)` extra space (or `O(n)` if considering recursion stack), where `n` is the number of nodes and `h` is the height of the tree.
Implement the function in Python. The input and output use dictionary-based nodes as described. No additional classes are required.
Constraints
The number of nodes in the tree is in the range `[0, 10^4]`. Node values are integers in the range `[-10^5, 10^5]`. `low` and `high` are integers with `low <= high`. The time complexity should be `O(n)`. The space complexity should be `O(h)` for recursion stack, but `O(n)` worst case is acceptable.
Example
```python
# Example 1:
# root = {'val': 3, 'left': {'val': 0, 'left': None, 'right': {'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': None}}, 'right': {'val': 4, 'left': None, 'right': None}}
# low = 1, high = 3
# Expected output (dictionary): {'val': 3, 'left': {'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': None}, 'right': None}
# Example 2:
# root = {'val': 1, 'left': {'val': 0, 'left': None, 'right': None}, 'right': {'val': 2, 'left': None, 'right': None}}
# low = 1, high = 2
# Expected output: {'val': 1, 'left': None, 'right': {'val': 2, 'left': None, 'right': None}}
# Example 3:
# root = {'val': 1, 'left': None, 'right': {'val': 2, 'left': None, 'right': None}}
# low = 2, high = 4
# Expected output: {'val': 2, 'left': None, 'right': None}
```
25 points
~25 min