Back to Search Start Over

Efficient reconstruction of binary trees from their traversals

Authors :
R.D. Cameron
Binay K. Bhattacharya
E.A.T. Merks
Source :
Applied Mathematics Letters. (1):79-82
Publisher :
Published by Elsevier Ltd.

Abstract

Given the n nodes of a binary tree in both inorder and preorder sequence, the tree can be uniquely identified. An efficient algorithm for reconstructing such trees from their sequences is presented, using O (n) time and O (h) intermediate storage, where h is the height of the tree being reconstructed.

Subjects

Subjects :
Combinatorics
Discrete mathematics
Tree traversal
AVL tree
K-ary tree
Binary tree
Applied Mathematics
Scapegoat tree
Interval tree
Random binary tree
Mathematics
Range tree

Details

Language :
English
ISSN :
08939659
Issue :
1
Database :
OpenAIRE
Journal :
Applied Mathematics Letters
Accession number :
edsair.doi.dedup.....3a69a78f7d21e51e6c49bb1342d0088b
Full Text :
https://doi.org/10.1016/0893-9659(89)90122-5
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details