A note on the reconstruction of a binary tree from its traversals

DOI10.1016/0020-0190(92)90100-AMaRDI QIDQ1198039zbMATH OpenWikidataFDO

Authors Naveen Gabrani, Priti Shankar

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90100-A

zbMATH Keywords

analysis of algorithmsbinary treeEREW PRAM modellinear-time sequential algorithmparallel algorithmpreorder and inorder traversalstree traversal

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Two algorithms for constructing a binary tree from its traversals
• Efficient reconstruction of binary trees from their transversals
• An optimal algorithm for reconstructing a binary tree
• Reconstructing a binary tree from its traversals in doubly logarithmic CREW time
• Constructing a binary tree efficiently from its traversals

Cites work

• Construction of a tree from its traversals in optimal time and space
• Listing and counting subtrees of equal size of a binary tree
• Parallel Prefix Computation
• Two algorithms for constructing a binary tree from its traversals

Cited in

(11)

• Two algorithms for constructing a binary tree from its traversals
• An optimal algorithm for reconstructing a binary tree
• New algorithms for the LCA problem and the binary tree reconstruction problem
• Efficient algorithms for tree reconstruction
• Reconstructing a binary tree from its traversals in doubly logarithmic CREW time
• Efficient reconstruction of binary trees from their transversals
• Constructing a binary tree from its traversals by reversible recursion and iteration
• Rebuilding a tree from its traversals: a case study of program inversion
• Optimal binary search trees
• A bounded-space tree traversal algorithm
• Construction of a tree from its traversals in optimal time and space

This page was built for publication: A note on the reconstruction of a binary tree from its traversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198039)