#K73932. Trim a Binary Search Tree

    ID: 34085 Type: Default 1000ms 256MiB

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:

  1. 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 keyword null (without quotes) to represent missing nodes. An empty tree is given as [].
  2. 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