Reconstruct BST From Preorder Data

**coderbjk** · February 7, 2016, 8:01pm

Version 1.5.1 - Question 15.6

Why do we need to pass min value in the second solution? Isn’t passing the max enough?

**tsunghsienlee** · February 8, 2016, 7:08pm

Hey,

I checked the C++ code on github page, and you shall notice that we actually use min value (i.e., lower_bound) to decide how algorithm should progress. You can check the implementation for more detail, and let me know if you have any problem.

**coderbjk** · February 7, 2016, 10:16pm

Yes, it uses the min value. What I am asking is whether we really need to check against min value. It looks like removing the min parameter and min check altogether will give the same output assuming the input is valid. We are not verifying the input anyways. Max check is obviously necessary.

**tsunghsienlee** · February 8, 2016, 7:18pm

I think min and max values are not use for verifying input, it is used to check the root value is within the subtree we are processing now or not. If the root value is within [min, max], it means this root value is in the subtree; otherwise, this root value is within another subtree.

Please take a look of the text and code, and let me know if you have any other problem.

**fondant** · March 11, 2018, 12:48am

I agree with @coderbjk
I don’t think the lower bound needs to be passed. If some value in the preorder sequence were to violate the lower bound, that would be a violation of the BST property. We shouldn’t need to pass a range. Passing the upper bound should be enough.