Reconstruct BST From Preorder Data

#1

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?

0 Likes

#2

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.

0 Likes

#3

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.

0 Likes

#4

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.

0 Likes

#5

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.

0 Likes