Document Type: Research Paper
Department of Engineering, School of Computer Science, New Jersey Institute of Technology, Newark, New Jersey, the USA.
Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands.
Department of Engineering Science, Golpayegan University of Technology, Golpayegan, Iran.
Binary trees are essential structures in Computer Science. The leaf (leaves) of a binary tree is one of the most significant aspects of it. In this study, we prove that the order of a leaf (leaves) of a binary tree is the same in the main tree traversals; preorder, inorder, and postorder. Then, we prove that given the preorder and postorder traversals of a binary tree, the leaf (leaves) of a binary tree can be determined. We present the algorithm BT-LEAF, a novel one, to detect the leaf (leaves) of a binary tree from its preorder and postorder traversals in quadratic time and linear space.