Constructing a binary tree efficiently from its traversals

Abstract

In this note we streamline an earlier algorithm for constructing a binary tree from its inorder and preorder traversals. The new algorithm is conceptually simpler than the earlier algorithms and its time complexity has a smaller constant facto.

Keywords:

• Algorithms
• Binary trees
• Tree traversals

C.R. Categories:

• E.1
• F.2

^∗Work supported by the Academy of Finland (Project 35025)email url="[email protected]"/>

^∗Work supported by the Academy of Finland (Project 35025)email url="[email protected]"/>

Notes

^∗Work supported by the Academy of Finland (Project 35025)email url="[email protected]"/>