Stack-based breadth-first search tree traversal

From the developerWorks archives

Pravin Kumar Sinha

Date archived: April 18, 2019 | First published: June 04, 2013

This article explains the traditional breadth-first search (BFS) that has drawbacks in terms of extra space required by the queue data structure. If a tree has multiple children and is a balanced tree, then the queue size would grow exponentially and could cause serious memory threats. The solution in this article provides a parallel approach for printing the tree in BFS fashion, where the queue data structure in not required at all. Instead, stack memory is used but memory consumption would be log(n) with base N, where N is the average children count per node and 'n' is the number of nodes in the tree.

This content is no longer being updated or maintained. The full article is provided "as is" in a PDF file. Given the rapid evolution of technology, some content, steps, or illustrations may have changed.



static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=AIX and UNIX
ArticleID=932384
ArticleTitle=Stack-based breadth-first search tree traversal
publish-date=06042013