Efficient reconstruction of binary trees from their traversals

AbstractGiven the n nodes of a binary tree in both inorder and preorder sequence, the tree can be uniquely identified. An efficient algorithm for reconstructing such trees from their sequences is presented, using O (n) time and O (h) intermediate storage, where h is the height of the tree being reconstructed