#K73932. Trim a Binary Search Tree
Trim a Binary Search Tree
Trim a Binary Search Tree
You are given a Binary Search Tree (BST) and two integers \(L\) and \(R\). Your task is to trim the BST such that all its elements lie in the inclusive range \([L, R]\). The resulting tree must remain a valid BST.
You need to perform the following operations:
- Remove nodes whose values are less than \(L\) or greater than \(R\).
- Preserve the relative structure of the remaining nodes.
- After trimming, output the inorder traversal of the BST.
Note: Inorder traversal of a BST yields sorted order of the nodes.
inputFormat
The input is provided via standard input (stdin) and consists of two lines:
- The first line is a string representing the level-order traversal of the tree in the form of a list. For example:
[10,5,15,2,7,12,20]
. Use the keywordnull
(without quotes) to represent missing nodes. An empty tree is given as[]
. - The second line contains two space-separated integers, \(L\) and \(R\), representing the lower and upper bounds of the range.
It is guaranteed that the input tree represents a valid binary tree.
outputFormat
Output the inorder traversal of the trimmed BST via standard output (stdout) in a single line. Print the node values separated by a single space. If the resulting tree is empty, output an empty line.
## sample[10,5,15,2,7,12,20]
5 15
5 7 10 12 15