First try

Check during the traverse. Time complexity is O(n), n is the number of
nodes. Another approach is to set a range to check the left and right,
the checking of left change the upper of range; the checking of right
change the lower of range