University of TehranJournal of Algorithms and Computation2476-277649220171130A novel algorithm to determine the leaf (leaves) of a binary tree from its preorder and postorder traversals1117972ENN.AghaieabianeDepartment of Engineering, School of Computer Science, New Jersey Institute of Technology,
Newark, New Jersey, the USA.H.KoppelaarFaculty of Electrical Engineering, Mathematics and Computer Science, Delft University of
Technology, Delft, The Netherlands.0000-0001-7487-6564PeymanNasehpourDepartment of Engineering Science, Golpayegan University of Technology, Golpayegan, Iran.Journal Article20170630Binary 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.https://jac.ut.ac.ir/article_7972_996a4abc640c11c9bc81d345f8955a5b.pdf