The work described in this paper presents an original hierarchical protocol based on the Partitioned Binary Search Tree (PBST*). PBST* is a new tree-based scalable distributed data structure. The principal feature of the proposed protocol is the organization of WSN as a balanced tree with one root at the base station (BS). Moreover, the protocol proposes a new technique to avoid the hot spot problem and allows to achieve more balanced energy consumption between the different Cluster-Heads. Also, it uses an energy criterion to elect optimal Cluster-Heads in each round. Experimental results demonstrate that the proposed protocol prolongs the network lifetime and the packet delivery ratio as compared to the LEACH-C protocol. The enhancement reaches 20.84% for the first node death, 43.45% for the last node death, while the packet delivery ratio is enhanced by up to 43.07%.