Based on our previous post we are at a prime point to deal with InOrder and PostOrder traversals for Binary Trees.

The beauty of unlocking one of these Depth-first search methods, is that you quickly seee the pattern and recognize that cuttting and pasting existing methods with some minor re-adjustment in order will result in InOrder and PostOrder traversals. Now what I am saying may sound a little abstract, but it will make more sense when you see the code. The important thing is not to recognize the pattern and memorize it (restructuring of the code that is), but rather what the ordering process of traversing the tree actually entails.

__Definition: InOrder__

- Traverse the left tree
- Display the value of root
- Traverse the right tree

Said differently, first visit the left sub-tree of root, from the extreme left and traverse all it’s children. Then visit the root node and get it’s value. Then visit the right sub-tree of root, from the extreme left and traverse all it’s children. By “extreme” I mean, keep going left until there is no left-node anymore.

Seeing this visually and relational to the tree (image) that features this article, InOrder would result in the following tree traversal:

**m, b, p, k, t, d, a, g, c, f, h**

Here is the code, and what you will immediately notice, it’s exactly like PreOrder except

- When the root node is visited has changed (inorder method itself)
- When the value is read (in the private inorder_subtree method)

__Unit Test:
__

it 'should return values in inorder' do expect(@bst.inorder(@bst)).to eq ['m', 'b', 'p', 'k', 't', 'd', 'a', 'g', 'c', 'f', 'h'] end

__Implementation:__

def inorder(node) result = [] result << inorder_subtree(node.root.left) result << @root.value result << inorder_subtree(node.root.right) result.flatten end

def inorder_subtree(node, result = []) inorder_subtree(node.left, result) if node.left != nil result << node.value inorder_subtree(node.right, result) if node.right != nil result end

Excellent.

__Definition: PostOrder__

- Traverse the left tree
- Traverse the right tree
- Display the value of root

I’m not going to into much more detail than that as the pattern now should be rather obvious. Here’s the code.

__Unit Test:__

it 'should return values in postorder' do expect(@bst.postorder(@bst)).to eq ['m', 'p', 't', 'k', 'b', 'g', 'a', 'h', 'f', 'c', 'd'] end

__Implementation:__

def postorder(node) result = [] result << postorder_subtree(node.root.left) # traverse left sub-tree result << postorder_subtree(node.root.right) # traverse right sub-treeresult.flatten result << @root.value # moved to end result.flatten end

def postorder_subtree(node, result = []) postorder_subtree(node.left, result) if node.left != nil postorder_subtree(node.right, result) if node.right != nil result << node.value # value read after left and right leafs reached result end

And there you have it.