Les nœuds dans un arbre de recherche binaire qui s'étend sur une plage

Question

J'ai un arbre de recherche binaire de hauteur $ h $ avec un entier dans chaque feuille. J'ai aussi une gamme $ [ ell, u] $. Je veux trouver un ensemble de nœuds qui s'étendent sur la gamme $ [ ell, u] $, c'est-à-dire, un ensemble $ S $ de nœuds tels que les feuilles sous $ S $ former tous (et seulement) ces feuilles contenant des entiers dans la gamme $ [ ell, u] $. Quelle est la taille $ S $ besoin d'être, dans le pire des cas, en fonction de la hauteur $ h $? Comment trouver un tel ensemble explicitement?