See we don't need to find all the possible local minimum the above logic will find atleast one local minimum.
Since all the labels are distinct it is pretty sure that in one of paths from root to leaf their exist a local minimum. In short we don't care what other minimums are.
You may have a question also that what if leaf itself not local minimum so we need to check other paths also ?
See the above case will never happen because we are going down only when it is lesser than parent so in worst case leaf node will definitely be local minimum.