level-order traversal

(algorithm)

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.

Note: 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:

 levelorderAux(tree, level)
 begin
     if tree is null, return;

     if level is 1, then
         print(tree.root);
     else if level greater than 1, then
         levelorderAux(tree.left_subtree, level-1);
         levelorderAux(tree.right_subtree, level-1);
     endif
 end
 
 levelorder(tree)
 begin
     for d = 1 to height(tree)
         levelorderAux(tree, d);
     endfor
 end 

See [Stand98, p. 251].

Author: PEB

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 17 December 2004.
HTML page formatted Mon Apr 23 09:23:15 2007.

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. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/levelOrderTraversal.html