To traverse a nonempty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:
(This is also called Depthfirst traversal.)
To traverse a nonempty binary tree in inorder, perform the following operations recursively at each node, starting with the root node:
To traverse a nonempty binary tree in postorder, perform the following operations recursively at each node, starting with the root node:
Finally, trees can also be traversed in levelorder, where we visit every node on a level before going to a lower level. This is also called Breadthfirst traversal.
In this binary search tree,

preorder(node)
print node.value
if node.left ≠ null then preorder(node.left)
if node.right ≠ null then preorder(node.right)
inorder(node)
if node.left ≠ null then inorder(node.left)
print node.value
if node.right ≠ null then inorder(node.right)
postorder(node)
if node.left ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
print node.value
All sample implementations will require stack space proportional to the height of the tree. In a poorly balanced tree, this can be quite considerable.
We can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree. In the case of using threads, this will allow for greatly improved inorder traversal, although retrieving the parent node required for preorder and postorder traversal will be slower than a simple stack based algorithm.
To traverse a threaded tree inorder, we could do something like this:
inorder(node)
while hasleftchild(node) do
node = node.left
do
visit(node)
if (hasrightchild(node)) then
node = node.right
while hasleftchild(node) do
node = node.left
else
node = node.right
while node ≠ null
Note that a threaded binary tree will provide a means of determining whether a pointer is a child, or a thread. See threaded binary trees for more information.
Level order traversal is a traversal method by which levels are visited successively starting with level 0 (the root node), and nodes are visited from left to right on each level.
This is commonly implemented using a queue data structure with the following steps (and using the tree below as an example):
Step 1: Push the root node onto the queue (node 2):
New queue: 2         
Step 2:
Pop the node off the front of the queue (node 2).
Push that node's left child onto the queue (node 7).
Push that node's right child onto the queue (node 5).
Output that node's value (2).
New queue: 75        
Output: 2
Step 3:
Pop the node off the front of the queue (node 7).
Push that node's left child onto the queue (node 2).
Push that node's right child onto the queue (node 6). Output that node's value (7).
New queue: 526       
Output: 2 7
Step 4:
Pop the node off the front of the queue (node 5). Push that node's left child onto the queue (NULL, so take no action). Push that node's right child onto the queue (node 9). Output that node's value (5).
New queue: 269       
Output: 2 7 5
Step 5:
Pop the node off the front of the queue (node 2).
Push that node's left child onto the queue (NULL, so take no action).
Push that node's right child onto the queue (NULL, so take no action).
Output that node's value (2).
New queue: 69        
Output: 2 7 5 2
Step 6:
Pop the node off the front of the queue (node 6).
Push that node's left child onto the queue (node 5).
Push that node's right child onto the queue (node 11).
Output that node's value (6).
New queue: 9511       
Output: 2 7 5 2 6
Step 7:
Pop the node off the front of the queue (node 9).
Push that node's left child onto the queue (node 4).
Push that node's right child onto the queue (NULL, so take no action).
Output that node's value (9).
New queue: 5114       
Output: 2 7 5 2 6 9
Step 8: You will notice that because the remaining nodes in the queue have no children, nothing else will be added to the queue, so the nodes will just be popped off and output consecutively (5, 11, 4). This gives the following:
Final output: 2 7 5 2 6 9 5 11 4
which is a levelorder traversal of the tree.
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.empty do
node := q.dequeue()
visit(node)
if node.left ≠ null
q.enqueue(node.left)
if node.right ≠ null
q.enqueue(node.right)
Inorder traversal
It is particularly common to use an inorder traversal on a binary search tree because this will return values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).
To see why this is the case, note that if n is a node in a binary search tree, then everything in n 's left subtree is less than n, and everything in n 's right subtree is greater than or equal to n. Thus, if we visit the left subtree in order, using a recursive call, and then visit n, and then visit the right subtree in order, we have visited the entire subtree rooted at n in order. We can assume the recursive calls correctly visit the subtrees in order using the mathematical principle of structural induction. Traversing in reverse inorder similarly gives the values in decreasing order.
Preorder traversal
Traversing a tree in preorder while inserting the values into a new tree is common way of making a complete copy of a binary search tree.
One can also use preorder traversals to get a prefix expression (Polish notation) from expression trees: traverse the expression tree preorderly. To calculate the value of such an expression: scan from right to left, placing the elements in a stack. Each time we find an operator, we replace the two top symbols of the stack with the result of applying the operator to those elements. For instance, the expression ∗ + 234, which in infix notation is (2 + 3) ∗ 4, would be evaluated like this:
Expression (remaining)  Stack 

∗ + 234  
∗ + 23  4 
∗ + 2  3 4 
∗ +  2 3 4 
∗  5 4 
Answer  20 
data Tree a = Nil  Node (Tree a) a (Tree a)
preorder Nil = []
preorder (Node left x right) = [x] ++ (preorder left) ++ (preorder right)
postorder Nil = []
postorder (Node left x right) = (postorder left) ++ (postorder right) ++ [x]
inorder Nil = []
inorder (Node left x right) = (inorder left) ++ [x] ++ (inorder right)
A sample is shown here for postorder traversal:
nonrecursivepostorder (rootNode)
nodeStack.push (rootNode)
while (!nodeStack.empty())
currNode = nodeStack.last ()
if ((currNode.left != null) and (currNode.left.visited == false))
nodeStack.push (currNode.left)
else
if ((currNode.right != null) and (currNode.right.visited == false))
nodeStack.push (currNode.right)
else
print currNode.value
currNode.visited := true
nodeStack.pop ()
In this case, for each node is required to keep an additional "visited" flag, other than usual informations (value, leftchildreference, rightchildreference).