Editing Tree traversal (section)

===Depth-first search===
{{Main|Depth-first search}}
[[File:Sorted binary tree ALL RGB.svg|thumb|293px|Depth-first traversal (dotted path) of a binary tree:{{ubl
| ''Pre-order (node visited at position red {{colorbull|#FF0000|round|size=180}})'':{{br}} &nbsp; &nbsp; F, B, A, D, C, E, G, I, H;
| ''In-order (node visited at position green {{colorbull|#00FF00|round|size=180}})'':{{br}} &nbsp; &nbsp; A, B, C, D, E, F, G, H, I;
| ''Post-order (node visited at position blue {{colorbull|#2A7FFF|round|size=180}})'':{{br}} &nbsp; &nbsp; A, C, E, D, B, H, I, G, F.
}}]]
In ''depth-first search'' (DFS), the search tree is deepened as much as possible before going to the next sibling.

To traverse binary trees with depth-first search, perform the following operations at each node:<ref>[http://www.cise.ufl.edu/~sahni/cop3530/slides/lec216.pdf ''Binary Tree Traversal Methods'']</ref><ref>{{cite web|url=http://www.programmerinterview.com/index.php/data-structures/preorder-traversal-algorithm/|title=Preorder Traversal Algorithm|access-date=2 May 2015}}</ref>
# If the current node is empty then return.
# Execute the following three operations in a certain order:<ref>L before R means the (standard) counter-clockwise traversal—as in the figure.<br />The execution of N before, between, or after L and R determines one of the described methods.<br />If the traversal is taken the other way around (clockwise) then the traversal is called reversed. This is described in particular for [[#Reverse in-order|reverse in-order]], when the data are to be retrieved in descending order.</ref>
#: N: Visit the current node.
#: L: Recursively traverse the current node's left subtree.
#: R: Recursively traverse the current node's right subtree.

The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited node. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely. Given a tree with distinct elements, either pre-order or post-order paired with in-order is sufficient to describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.<ref>{{cite web|url=https://cs.stackexchange.com/q/439 |title=Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange|access-date=2 May 2015}}</ref>

There are three methods at which position of the traversal relative to the node (in the figure: red, green, or blue) the visit of the node shall take place. The choice of exactly one color determines exactly one visit of a node as described below. Visit at all three colors results in a threefold visit of the same node yielding the “all-order” sequentialisation:
:{{font color|red|F}}-{{font color|red|B}}-{{font color|red|A}}-{{font color|green|A}}-{{font color|#2A7FFF|A}}-{{font color|green|B}}-{{font color|red|D}}-{{font color|red|C}}-{{font color|green|C}}-{{font color|#2A7FFF|C}}-{{font color|green|D}}-{{font color|red|E}}-{{font color|green|E}}-{{font color|#2A7FFF|E}}-{{font color|#2A7FFF|D}}-{{font color|#2A7FFF|B}}-{{font color|green|F}}-{{font color|red|G}}-{{font color|green|G}}-{{font color|red|&thinsp;I}}-{{font color|red|H}}-{{font color|green|H}}-{{font color|#2A7FFF|H}}-{{font color|green|&thinsp;I}}-{{font color|#2A7FFF|&thinsp;I}}-{{font color|#2A7FFF|G}}-{{font color|#2A7FFF|F}}

===={{anchor|Preorder traversal|Pre-order traversal}}Pre-order, NLR====
# Visit the current node (in the figure: position red).
# Recursively traverse the current node's left subtree.
# Recursively traverse the current node's right subtree.

The pre-order traversal is a [[Topological sorting|topologically sorted]] one, because a parent node is processed before any of its child nodes is done.

===={{anchor|Postorder traversal|Post-order traversal}}Post-order, LRN====
# Recursively traverse the current node's left subtree.
# Recursively traverse the current node's right subtree.
# Visit the current node (in the figure: position blue).

Post-order traversal can be useful to get [[Reverse_Polish_notation|postfix expression]] of a [[binary expression tree]].

===={{anchor|Inorder traversal|In-order traversal}}In-order, LNR====
# Recursively traverse the current node's left subtree.
# Visit the current node (in the figure: position green).
# Recursively traverse the current node's right subtree.

In a [[binary search tree]] ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ''ascending'' sorted order.<ref>{{cite web |url=https://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |website=[[UCLA]] Math |last=Wittman |first=Todd |access-date=January 2, 2016 |title=Tree Traversal |url-status=dead |archive-url=https://web.archive.org/web/20150213195803/http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |archive-date=February 13, 2015 }} </ref>

===={{anchor|Reverse preorder traversal|Reverse pre-order traversal}}Reverse pre-order, NRL====
# Visit the current node.
# Recursively traverse the current node's right subtree.
# Recursively traverse the current node's left subtree.

===={{anchor|Reverse postorder traversal|Reverse post-order traversal}}Reverse post-order, RLN====
# Recursively traverse the current node's right subtree.
# Recursively traverse the current node's left subtree.
# Visit the current node.

===={{anchor|Reverse inorder traversal|Reverse in-order traversal}}Reverse in-order, RNL====
# Recursively traverse the current node's right subtree.
# Visit the current node.
# Recursively traverse the current node's left subtree.

In a [[binary search tree]] ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, reverse in-order traversal retrieves the keys in ''descending'' sorted order.

====Arbitrary trees====
To traverse arbitrary trees (not necessarily binary trees) with depth-first search, perform the following operations at each node:
# If the current node is empty then return.
# Visit the current node for pre-order traversal.
# For each ''i'' from 1 to the current node's number of subtrees − 1, or from the latter to the former for reverse traversal, do:
## Recursively traverse the current node's ''i''-th subtree.
## Visit the current node for in-order traversal.
# Recursively traverse the current node's last subtree.
# Visit the current node for post-order traversal.

Depending on the problem at hand, pre-order, post-order, and especially one of the number of subtrees − 1 in-order operations may be optional. Also, in practice more than one of pre-order, post-order, and in-order operations may be required. For example, when inserting into a ternary tree, a pre-order operation is performed by comparing items. A post-order operation may be needed afterwards to re-balance the tree.