Construction of a tree from its traversals in optimal time and space

DOI10.1016/0020-0190(90)90224-LMaRDI QIDQ910183zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 1990

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

Full work available at URL https://doi.org/10.1016/0020-0190(90)90224-l

zbMATH Keywords

analysis of algorithmsbinary search treetree constructiontree traversaldata struturesmultiway tree

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6622715
• Efficient algorithms for tree reconstruction
• Two algorithms for constructing a binary tree from its traversals
• A note on the reconstruction of a binary tree from its traversals
• Constructing a binary tree efficiently from its traversals

Cites work

• Multidimensional binary search trees used for associative searching
• Optimum binary search trees
• Two algorithms for constructing a binary tree from its traversals

Cited in

(16)

• A bounded-space tree traversal algorithm
• Building Optimal Binary Search Trees from Sorted Values in O(N) Time
• Linear-time construction of treaps and Cartesian trees
• scientific article; zbMATH DE number 6622715 (Why is no real title available?)
• Execution time analysis of a top-down R-tree construction algorithm
• Constant-memory iterative generation of special strings representing binary trees
• Constructing a binary tree efficiently from its traversals
• Constant Time Generation of Free Trees
• An optimal algorithm for reconstructing a binary tree
• Constructing a minimum height elimination tree of a tree in linear time
• Constructing a binary tree from its traversals by reversible recursion and iteration
• New algorithms for the LCA problem and the binary tree reconstruction problem
• Two algorithms for constructing a binary tree from its traversals
• A note on the reconstruction of a binary tree from its traversals
• Efficient algorithms for tree reconstruction
• Reconstructing a binary tree from its traversals in doubly logarithmic CREW time

This page was built for publication: Construction of a tree from its traversals in optimal time and space

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