Linear Time and Space Reconstruction of a Binary Tree from Its Pre-Order and In-Order Traversals

Abstract

In this paper, a new idea using some special data structure for the reconstruction of a binary tree from its pre-order and in-order traversals in linear time and space is presented. The reconstruction of the binary tree from its in-order and post-order traversals is also studied.