A novel algorithm to determine the leaf (leaves) of a binary tree from its preorder and postorder traversals

Document Type : Research Paper

Authors

1 Department of Engineering, School of Computer Science, New Jersey Institute of Technology, Newark, New Jersey, the USA.

2 Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands.

3 Department of Engineering Science, Golpayegan University of Technology, Golpayegan, Iran.

Abstract

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.

Keywords

Files

Share

How to cite

Statistics