Definition: Process all nodes of a tree by depth: first the root, then the children of the root, etc. Equivalent to a breadth-first search from the root.
See also postorder traversal, preorder traversal, tree traversal, level.
For instance, if the "processing" is just printing, a tree is printed as "root, all children of the root, all grandchildren (children of children) of the root, etc." Here is pseudocode for an inefficient level-order traversal of a binary tree:
if tree is null, return;
if level is 1, then
else if level greater than 1, then
for d = 1 to height(tree)
See [Stand98, p. 251].
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 26 May 2011.
HTML page formatted Thu May 26 15:59:49 2011.
Cite this as:
Paul E. Black, "level-order traversal", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/levelOrderTraversal.html