TreeTraversalOrder

TreeTraversalOrder

is an option for TreeMap and related functions that specifies the order to visit subtrees.

Details

  • Traversing a tree is also known as scanning a tree or tree search. A traversal order specifies the order subtrees are visited in functions such as TreeMap and TreeScan.
  • There are many different traversal orders and variants, including pre-, in-, and post-order depth-first traversals and breadth-first traversals.
  • General settings for TreeTraversalOrder can be given as:
  • Automaticuse the default traversal order
    {tspec,vspec,hspec}base order tspec, vertical order vspec, horizontal order hspec
    specany subset of tspec, vspec, hspec, with defaults for the rest
  • Settings for the base order tspec include:
  • "DepthFirst"traverse the entire subtree before traversing its next sibling
    "BreadthFirst","LevelOrder"visit nodes by level starting from the root
    "LeavesFirst"visit nodes by level starting from the leaves
  • The relevant disjoint sets of nodes for base orders tspec are:
  • Settings for the vertical order vspec include:
  • "TopDown","OuterInner","PreOrder"visit parents before their children, starting from the root
    "BottomUp","InnerOuter","PostOrder"visit children before their parents, starting from the leaves
  • Additional settings for the vertical order vspec for "DepthFirst" tspec include:
  • "InOrder"visit parents after their first children
  • Settings for the horizontal order hspec include:
  • "LeftRight"visit nodes from left to right
    "RightLeft"visit nodes from right to left
  • If tspec is not specified, "DepthFirst" is used.
  • If vspec is Automatic or not specified, "BottomUp" is used for "DepthFirst" and "LeavesFirst" tspec, following the standard behavior of Map and Scan. For "BreadthFirst" tspec, "TopDown" is used, following standard practice.
  • If hspec is not specified, "LeftRight" is used.

Examples

open allclose all

Basic Examples  (3)

Number the nodes of a tree as they are visited in a depth-first traversal order:

Specify a breadth-first traversal:

Specify the vertical order for a base traversal:

Scope  (18)

Base Order  (14)

"DepthFirst"  (6)

A depth-first traversal visits nodes in a left-to-right, bottom-up order by default:

Specify a pre-order, depth-first traversal:

Specify an in-order, depth-first traversal:

By default, a post-order, depth-first traversal is used:

Visit parents after their first children:

Specify a right-to-left, depth-first traversal:

By default, a left-to-right, depth-first traversal is used:

Specify the vertical and horizontal orders for a depth-first traversal:

Make a grid of all depth-first traversal variants:

"BreadthFirst"  (4)

A breadth-first traversal visits nodes by level starting from the root:

"LevelOrder" is equivalent:

Specify a bottom-up, breadth-first traversal:

By default, a top-down order is used:

Specify the vertical and horizontal orders for a breadth-first traversal:

Make a grid of all breadth-first traversal variants:

"LeavesFirst"  (4)

A leaves-first traversal visits nodes by level starting from the leaves:

Specify a top-down, leaves-first traversal:

By default, a bottom-up order is used:

Specify the vertical and horizontal orders for a leaves-first traversal:

Make a grid of all leaves-first traversal variants:

Vertical Order  (2)

Top-down traversal:

Bottom-up traversal:

Horizontal Order  (2)

Left-to-right traversal:

Right-to-left traversal

Properties & Relations  (5)

Compare bottom-up variants of depth-first, breadth-first and leaves-first traversals:

Compare top-down variants of depth-first, breadth-first and leaves-first traversals:

A pre-order, depth-first traversal corresponds to the leftmost, outermost order of the positions:

Lexicographic order puts positions in numerical order first, then in order of increasing length:

A breadth-first traversal corresponds to the outermost, leftmost order of the positions:

Canonical order puts positions in order of increasing length first, then in numerical order:

A bottom-up, left-to-right traversal order is the reverse of a top-down, right-to-left traversal order:

Wolfram Research (2021), TreeTraversalOrder, Wolfram Language function, https://reference.wolfram.com/language/ref/TreeTraversalOrder.html (updated 2024).

Text

Wolfram Research (2021), TreeTraversalOrder, Wolfram Language function, https://reference.wolfram.com/language/ref/TreeTraversalOrder.html (updated 2024).

CMS

Wolfram Language. 2021. "TreeTraversalOrder." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2024. https://reference.wolfram.com/language/ref/TreeTraversalOrder.html.

APA

Wolfram Language. (2021). TreeTraversalOrder. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/TreeTraversalOrder.html

BibTeX

@misc{reference.wolfram_2024_treetraversalorder, author="Wolfram Research", title="{TreeTraversalOrder}", year="2024", howpublished="\url{https://reference.wolfram.com/language/ref/TreeTraversalOrder.html}", note=[Accessed: 22-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_treetraversalorder, organization={Wolfram Research}, title={TreeTraversalOrder}, year={2024}, url={https://reference.wolfram.com/language/ref/TreeTraversalOrder.html}, note=[Accessed: 22-December-2024 ]}