public/*print items satisfying low < <high and low < <high *void printrangeconst vector lowconst vector high const printrangelowhighroot )privatevoid printrangeconst vector lowconst vector highkdnode *tint level const ift !nullptr iflow data &high > ->data &low data &high > ->data cout data <",data <")<endliflowlevel datalevel printrangelowhight->left level )ifhighlevel > ->datalevel printrangelowhight->right level )figure - treesrange search treethe worst-case running time of range query is ( kn - / in randomly constructed - treea partial match query that involves of the keys takes ( na )where is the (onlypositive root of ( ) ( ) - computation of for various and is left as an exercisethe value for and is reflected in the result stated above for partial matching in random - trees although there are several exotic structures that support range searchingthe - tree is probably the simplest such structure that achieves respectable running times