TY - JOUR ID - 7972 TI - A novel algorithm to determine the leaf (leaves) of a binary tree from its preorder and postorder traversals JO - Journal of Algorithms and Computation JA - JAC LA - en SN - 2476-2776 AU - Aghaieabiane, N. AU - Koppelaar, H. AU - Nasehpour, Peyman AD - Department of Engineering, School of Computer Science, New Jersey Institute of Technology, Newark, New Jersey, the USA. AD - Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands. AD - Department of Engineering Science, Golpayegan University of Technology, Golpayegan, Iran. Y1 - 2017 PY - 2017 VL - 49 IS - 2 SP - 1 EP - 11 KW - Binary tree KW - Proper binary tree KW - Preorder traversal KW - Inorder traversal KW - Postorder traversal KW - time complexity KW - Space complexity DO - 10.22059/jac.2017.7972 N2 - 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. UR - https://jac.ut.ac.ir/article_7972.html L1 - https://jac.ut.ac.ir/article_7972_996a4abc640c11c9bc81d345f8955a5b.pdf ER -