Tree traversal
Graph and tree search algorithms 

Listings 

Related topics 
In computer science, tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well.
Types
Unlike linked lists, onedimensional arrays and other linear data structures, which are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in depthfirst or breadthfirst order. There are three common ways to traverse them in depthfirst order: inorder, preorder and postorder.^{[1]} Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depthlimited searches like iterative deepening depthfirst search.
Data structures for tree traversal
Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred—stored in some way for later visiting. This is often done via a stack (LIFO) or queue (FIFO). As a tree is a selfreferential (recursively defined) data structure, traversal can be defined by recursion or, more subtly, corecursion, in a very natural and clear fashion; in these cases the deferred nodes are stored implicitly in the call stack.
Depthfirst search is easily implemented via a stack, including recursively (via the call stack), while breadthfirst search is easily implemented via a queue, including corecursively.
Depthfirst search
These searches are referred to as depthfirst search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling. For a binary tree, they are defined as display operations recursively at each node, starting with the root, whose algorithm is as follows:^{[2]} ^{[3]}
The general recursive pattern for traversing a (nonempty) binary tree is this: At node N you must do these three things:
(L) Recursively traverse its left subtree. When this step is finished you are back at N again.
(R) Recursively traverse its right subtree. When this step is finished you are back at N again.
(N) Process N itself.
We may do these things in any order. If we do (L) before (R), we call it lefttoright traversal, otherwise we call it righttoleft traversal.
Preorder
 Check if the current node is empty / null
 Display the data part of the root (or current node).
 Traverse the left subtree by recursively calling the preorder function.
 Traverse the right subtree by recursively calling the preorder function.
Inorder
 Check if the current node is empty / null
 Traverse the left subtree by recursively calling the inorder function.
 Display the data part of the root (or current node).
 Traverse the right subtree by recursively calling the inorder function.
In a search tree, inorder traversal retrieves data in sorted order.^{[4]}
Postorder
 Check if the current node is empty / null
 Traverse the left subtree by recursively calling the postorder function.
 Traverse the right subtree by recursively calling the postorder function.
 Display the data part of the root (or current node).
The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited root. No one sequentialisation according to pre, in or postorder describes the underlying tree uniquely. Given a tree with distinct elements, either preorder or postorder paired with inorder is sufficient to describe the tree uniquely. However, preorder with postorder leaves some ambiguity in the tree structure.^{[5]}
Generic tree
To traverse any tree with depthfirst search, perform the following operations recursively at each node:
 Perform preorder operation.
 For each i from 1 to the number of children do:
 Visit ith, if present.
 Perform inorder operation.
 Perform postorder operation.
Depending on the problem at hand, the preorder, inorder or postorder operations may be void, or you may only want to visit a specific child, so these operations are optional. Also, in practice more than one of preorder, inorder and postorder operations may be required. For example, when inserting into a ternary tree, a preorder operation is performed by comparing items. A postorder operation may be needed afterwards to rebalance the tree.
Breadthfirst search
Trees can also be traversed in levelorder, where we visit every node on a level before going to a lower level. This search is referred to as breadthfirst search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.
Other types
There are also tree traversal algorithms that classify as neither depthfirst search nor breadthfirst search. One such algorithm is Monte Carlo tree search, which concentrates on analyzing the most promising moves, basing the expansion of the search tree on random sampling of the search space.
Applications
Preorder traversal while duplicating nodes and edges can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree preorderly.
Inorder traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).
Postorder traversal while deleting or freeing nodes and values can delete or free an entire binary tree. It can also generate a postfix representation of a binary tree.
Implementations
Depthfirst search
Preorder
preorder(node) if (node = null) return visit(node) preorder(node.left) preorder(node.right) 
iterativePreorder(node) if (node = null) return s ← empty stack s.push(node) while (not s.isEmpty()) node ← s.pop() visit(node) if (node.right ≠ null) s.push(node.right) if (node.left ≠ null) s.push(node.left) 
Inorder
inorder(node) if (node = null) return inorder(node.left) visit(node) inorder(node.right) 
iterativeInorder(node) s ← empty stack while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else node ← s.pop() visit(node) node ← node.right 
Postorder
postorder(node) if (node = null) return postorder(node.left) postorder(node.right) visit(node) 
iterativePostorder(node) s ← empty stack lastNodeVisited ← null while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else peekNode ← s.peek() // if right child exists and traversing node // from left child, then move right if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right) node ← peekNode.right else visit(peekNode) lastNodeVisited ← s.pop() 
All the above implementations require stack space proportional to the height of the tree which is a call stack for the recursive and a parent stack for the iterative ones. In a poorly balanced tree, this can be considerable. With the iterative implementations we can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree (next section).
Morris inorder traversal using threading
A binary tree is threaded by making every left child pointer (that would otherwise be null) point to the inorder predecessor of the node (if it exists) and every right child pointer (that would otherwise be null) point to the inorder successor of the node (if it exists).
Advantages:
 Avoids recursion, which uses a call stack and consumes memory and time.
 The node keeps a record of its parent.
Disadvantages:
 The tree is more complex.
 We can make only one traversal at a time.
 It is more prone to errors when both the children are not present and both values of nodes point to their ancestors.
Morris traversal is an implementation of inorder traversal that uses threading:^{[6]}
 Create links to the inorder successor.
 Print the data using these links.
 Revert the changes to restore original tree.
Breadthfirst search
Also, listed below is pseudocode for a simple queue based level order traversal, and will require space proportional to the maximum number of nodes at a given depth. This can be as much as the total number of nodes / 2. A more spaceefficient approach for this type of traversal can be implemented using an iterative deepening depthfirst search.
levelorder(root) q ← empty queue q.enqueue(root) while (not q.isEmpty()) node ← q.dequeue() visit(node) if (node.left ≠ null) q.enqueue(node.left) if (node.right ≠ null) q.enqueue(node.right)
Infinite trees
While traversal is usually done for trees with a finite number of nodes (and hence finite depth and finite branching factor) it can also be done for infinite trees. This is of particular interest in functional programming (particularly with lazy evaluation), as infinite data structures can often be easily defined and worked with, though they are not (strictly) evaluated, as this would take infinite time. Some finite trees are too large to represent explicitly, such as the game tree for chess or go, and so it is useful to analyze them as if they were infinite.
A basic requirement for traversal is to visit every node. For infinite trees, simple algorithms often fail this. For example, given a binary tree of infinite depth, a depthfirst search will go down one side (by convention the left side) of the tree, never visiting the rest, and indeed if inorder or postorder will never visit any nodes, as it has not reached a leaf (and in fact never will). By contrast, a breadthfirst (levelorder) traversal will traverse a binary tree of infinite depth without problem, and indeed will traverse any tree with bounded branching factor.
On the other hand, given a tree of depth 2, where the root has infinitely many children, and each of these children has two children, a depthfirst search will visit all nodes, as once it exhausts the grandchildren (children of children of one node), it will move on to the next (assuming it is not postorder, in which case it never reaches the root). By contrast, a breadthfirst search will never reach the grandchildren, as it seeks to exhaust the children first.
A more sophisticated analysis of running time can be given via infinite ordinal numbers; for example, the breadthfirst search of the depth 2 tree above will take ?·2 steps: ? for the first level, and then another ? for the second level.
Thus, simple depthfirst or breadthfirst searches do not traverse every infinite tree, and are not efficient on very large trees. However, hybrid methods can traverse any (countably) infinite tree, essentially via a diagonal argument ("diagonal"—a combination of vertical and horizontal—corresponds to a combination of depth and breadth).
Concretely, given the infinitely branching tree of infinite depth, label the root (), the children of the root (1), (2), …, the grandchildren (1, 1), (1, 2), …, (2, 1), (2, 2), …, and so on. The nodes are thus in a onetoone correspondence with finite (possibly empty) sequences of positive numbers, which are countable and can be placed in order first by sum of entries, and then by lexicographic order within a given sum (only finitely many sequences sum to a given value, so all entries are reached—formally there are a finite number of compositions of a given natural number, specifically 2^{n−1} compositions of n = 1), which gives a traversal. Explicitly:
0: () 1: (1) 2: (1, 1) (2) 3: (1, 1, 1) (1, 2) (2, 1) (3) 4: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)
etc.
This can be interpreted as mapping the infinite depth binary tree onto this tree and then applying breadthfirst search: replace the "down" edges connecting a parent node to its second and later children with "right" edges from the first child to the second child, from the second child to the third child, etc. Thus at each step one can either go down (append a (, 1) to the end) or go right (add one to the last number) (except the root, which is extra and can only go down), which shows the correspondence between the infinite binary tree and the above numbering; the sum of the entries (minus one) corresponds to the distance from the root, which agrees with the 2^{n−1} nodes at depth n − 1 in the infinite binary tree (2 corresponds to binary).
References
 ↑ "Lecture 8, Tree Traversal". Retrieved 2 May 2015.
 ↑ http://www.cise.ufl.edu/~sahni/cop3530/slides/lec216.pdf
 ↑ "Preorder Traversal Algorithm". Retrieved 2 May 2015.
 ↑ Wittman, Todd. "Tree Traversal" (PDF). UCLA Math. Archived from the original (PDF) on February 13, 2015. Retrieved January 2, 2016.
 ↑ "Algorithms, Which combinations of pre, post and inorder sequentialisation are unique?, Computer Science Stack Exchange". Retrieved 2 May 2015.
 ↑ Morris, Joseph M. (1979). "Traversing binary trees simply and cheaply". Information Processing Letters. 9 (5). doi:10.1016/00200190(79)900681.
 General
 Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition.
 Drozdek, Adam. "Data Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001. Second edition.
 http://www.math.northwestern.edu/~mlerma/courses/cs31005s/notes/dmtreetran
External links
 Animation Applet of Binary Tree Traversal
 The Adjacency List Model for Processing Trees with SQL
 Storing Hierarchical Data in a Database with traversal examples in PHP
 Managing Hierarchical Data in MySQL
 Working with Graphs in MySQL
 Sample code for recursive and iterative tree traversal implemented in C.
 Sample code for recursive tree traversal in C#.
 See tree traversal implemented in various programming language on Rosetta Code
 Tree traversal without recursion