Depth-first traversal of a tree

A depth-first traversal starts at a root, recursively visits each child subtree, and returns along the entering edge. On a finite tree, the resulting closed walk traverses each edge exactly once in each direction.

Visit all child subtrees before visiting their parent. A depth-first traversal of a tree produces this order by processing a node on return from its recursive calls. It lets dynamic programming use the already computed answers of every child subtree.

Visit a rooted tree's root before recursively visiting its child subtrees in their specified order. For a binary tree, the order is root, left subtree, right subtree. Unlike inorder traversal, this interpretation stores an internal node's label before either child's labels.