Tree traversal: Difference between revisions

Revision as of 05:34, 3 July 2023

Revision as of 06:20, 3 July 2023

Line 11:

Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred—stored in some way for later visiting. This is often done via a [[Stack (abstract data type)|stack]] (LIFO) or [[Queue (abstract data type)|queue]] (FIFO). As a tree is a self-referential (recursively defined) data structure, traversal can be defined by [[recursion]] or, more subtly, [[corecursion]], in a natural and clear fashion; in these cases the deferred nodes are stored implicitly in the [[call stack]].

Depth-first search is easily implemented via a stack, including recursively (via the call stack), while the breadth-first search is easily implemented via a queue, including corecursively.<ref name="Pfaff">{{cite book|last1=Pfaff|first1=Ben|title=An Introduction to Binary Search Trees and Balanced Trees|date=2004|publisher=Free Software Foundation, Inc.}}</ref>{{rp|45−61}}

===Depth-first search===