Due to the ever-increasing cybercrime and hazards on digital information stored or in transit over computer clouds and networks, so many encryption algorithms were developed and practically implemented. On the other hand, hackers and intruders keep on developing methods to break those algorithms. Hence, new methods are always sought and developed by researchers. A binary search tree (BST) is implemented in this paper to produce a new algorithm for image encryption. The BST is utilized to generate an encryption key that consists of two parts; local and global with flexible length capabilities that provide better security. Sharing all image contents to encrypt any byte of the source image helped to achieve Shannon’s concept of diffusion and confusion. The experimental application of this algorithm has manifested a satisfactory security performance as compared with the widely used cryptographic systems such as Advanced Encryption Standard (AES) and Data Encryption Standard (DES). These Comparisons included measurement of encryption time complexity, Peak Signal to Noise Ratio (PSNR), Entropy, encryption key space. Besides, the new method offers encryption key length flexibility and involvement of all image contents in its generation.