%0 Journal Article
%T A novel algorithm to determine the leaf (leaves) of a binary tree from its preorder and postorder traversals
%J Journal of Algorithms and Computation
%I University of Tehran
%Z 2476-2776
%A Aghaieabiane, N.
%A Koppelaar, H.
%A Nasehpour, Peyman
%D 2017
%\ 11/30/2017
%V 49
%N 2
%P 1-11
%! A novel algorithm to determine the leaf (leaves) of a binary tree from its preorder and postorder traversals
%K Binary tree
%K Proper binary tree
%K Preorder traversal
%K Inorder
traversal
%K Postorder traversal
%K time complexity
%K Space complexity
%R 10.22059/jac.2017.7972
%X 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.
%U https://jac.ut.ac.ir/article_7972_996a4abc640c11c9bc81d345f8955a5b.pdf