ScholarLens Back to search
2010•Unpublished venueRequires access

A New Non-recursive Algorithm for Reconstructing a Binary Tree from its Traversals

Vinu V. Das

Open publisher page 11 citations

Abstract

This paper presents a new non-recursive algorithm for reconstructing a binary tree from its traversals. Binary tree traversal refers to the process of visiting each node in a specified order. Given the in order traversal of a binary tree, along with one of its preorder or post order traversals, the original binary tree can be uniquely identified. This algorithm is efficient and requires O(n) time and O(n) space. The implementation of this algorithm was done in C and the complete algorithm was tested. The new algorithm was found to be faster than other non-recursive algorithms.

About this research paper

What this paper is about

This paper presents a new non-recursive algorithm for reconstructing a binary tree from its traversals. Binary tree traversal refers to the process of visiting each node in a specified order. Given the in order traversal of a binary tree, along with one of its preorder or post order traversals, the original binary tree can be uniquely identified. This algorithm is efficient and requires O(n) time and O(n) space. The implementation of this algorithm was done in C and the complete algorithm was tested. The new algorithm was found to be faster than other non-recursive algorithms.

Why it matters

OpenAlex reports 11 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

This paper presents a new non-recursive algorithm for reconstructing a binary tree from its traversals. Binary tree traversal refers to the process of visiting each node in a specified order. Given the in order traversal of a binary tree, along with one of its preorder or post order traversals, the original binary tree can be uniquely identified. This algorithm is efficient and requires O(n) time and O(n) space. The implementation of this algorithm was done in C and the complete algorithm was tested. The new algorithm was found to be faster than other non-recursive algorithms.

Key concepts: Tree traversal, Binary tree, Preorder, Algorithm, Tree (set theory), Binary number, Computer science, Binary search tree

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
A New Non-recursive Algorithm for Reconstructing a Binary Tree from its Traversals — Research Paper | ScholarLens