A new non-recursive algorithm for binary search tree traversal

Document Type

Conference Proceeding

Source of Publication

Proceedings of the IEEE International Conference on Electronics, Circuits, and Systems

Publication Date

12-1-2003

Abstract

Binary tree traversal refers to the process of visiting each node in a specified order. There are two ways to visit a tree: recursively and non-recursively. Most references introduce tree traversal using recursion only. Our literature survey indicated that most references only show the implementations of the recursive algorithms, and only few references address the issue of nonrecursive algorithms. In this paper we investigate (compare) recursive and non-recursive algorithms for inorder, preorder, and postorder traversals. The inorder traversal of a binary search tree is important in searching algorithms, operating systems, and compiler design. In this paper we propose a new non-recursive algorithm for inorder binary search trees that is both efficient and easy to understand. The implementation of this new algorithm was done in Java and the complete algorithm was tested. The new algorithm was found to be faster than other nonrecursive algorithm. © 2003.IEEE.

ISBN

0780381637

Publisher

IEEE

Volume

2

First Page

770

Last Page

773

Disciplines

Computer Sciences

Keywords

Binary search trees, Compiler design, Literature survey, Operating systems, Preorders, Recursions, Recursive algorithms, Searching algorithms, Tree traversal, Binary search trees, Compiler design, Literature survey, Post-order traversals, Recursions, Recursive algorithms, Searching algorithms, Tree traversal, Algorithms, Binary trees, Computer operating systems, Algorithms, Binary trees, Trees (mathematics), Trees (mathematics)

Scopus ID

77952011714

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS