Binary Tree: InOrder & PostOrder

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

  1. Traverse the left tree
  2. Display the value of root
  3. 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

  1. Traverse the left tree
  2. Traverse the right tree
  3. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *