The rapid growth of mobile phone technologies encourages many researchers to explore, design and develop mobile learning applications for tertiary students. In computer science related disciplines, students always find computer science concepts as complex, abstract, and esoteric subject. Hence, we have seen the number of students enrolled for computer science related programs has decreased lately. Current delivery methods of computer science concepts are also not so interesting to the students. This project focuses on the design and development of an AVL tree learning object for tertiary students by utilizing current mobile phone's features such as mobility, multimedia capability and connectivity. Our approach is to incorporate video clips that presenting the algorithm systematically. With this mobile learning application, student could learn at his or her own pace, anywhere at anytime. This application intends to complement current learning systems that are traditional classroom and e-learning systems. We applied prototype methodology in designing and developing this mobile learning application prototype and considered several mobile application design principles. Initial testing has shown that a well-presented video clip of AVL tree concept that delivered through mobile phone has a great potential to promote and enhance learning process.