Two algorithms for constructing a binary tree from its traversals

DOI10.1016/0020-0190(88)90177-9MaRDI QIDQ1111397zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1988

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

Full work available at URL https://doi.org/10.1016/0020-0190(88)90177-9

zbMATH Keywords

binary treedata structuretree traversal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

Given the inorder traversal of a binary tree, along with one of its preorder or postorder traversals, the original binary tree can be uniquely identified. We present two construction algorithms: one, which requires O(N) time, is time optimal but space inefficient, and the other requires O(N log N) time and O(N) space.

Recommendations

• A note on the reconstruction of a binary tree from its traversals
• Constructing a binary tree efficiently from its traversals
• Efficient reconstruction of binary trees from their transversals
• Construction of a tree from its traversals in optimal time and space
• An optimal algorithm for reconstructing a binary tree

Cites work

• A numbering system for binary trees
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Listing and counting subtrees of equal size of a binary tree

Cited in

(15)

• Efficient generation of binary trees from inorder-postorder sequences
• Inversion of a recursive tree traversal
• An optimal algorithm for reconstructing a binary tree
• A note on the reconstruction of a binary tree from its traversals
• New algorithms for the LCA problem and the binary tree reconstruction problem
• Constructing a binary tree from its traversals
• Efficient reconstruction of binary trees from their transversals
• Constructing a binary tree from its traversals by reversible recursion and iteration
• scientific article; zbMATH DE number 6622715 (Why is no real title available?)
• Constructing a binary tree efficiently from its traversals
• Rebuilding a tree from its traversals: a case study of program inversion
• Optimal binary search trees
• Construction of a tree from its traversals in optimal time and space
• Parallel general prefix computations with geometric, algebraic, and other applications
• A binary decision algorithm

This page was built for publication: Two algorithms for constructing 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 Q1111397)