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.

Depth First

Today we are looking at Binary Tree traversal, that is, what strategy will we use to descend up and down the tree to update or check the value at a node. There are two primary categorical traversal strategies, one being Depth-first search and the other Breadth-first search. Depth-first is basically about going deeper or descending into the tree, while Breadth-first search is traversal at level-order, that is the nodes that are at the same height spatially. For the purposes of narrowing our scope and not overloading our approach to learning, let’s just focus on one of Depth-first search approaches and that of PreOrder. So if that intro felt like an overload, skip right ahead, collect your R200 and let’s just plod on……

Definition of PreOrder Traversal:

  1. Display value of root
  2. Traverse the left tree 
  3. Traverse the right tree
 
Said differently, first visit the root node (and get it’s value), then traverse it’s left sub-tree; starting from the left and traverse all the children. Then switch to the right sub-tree; starting from the left, and traverse all the children.
Make sense? Ok, let’s go visual.
If we applied PreOrder traversal to the Binary Tree listed above by following the 3 rules in its definition; our end result is
d, b, m, k, p, t, c, a, g, f, h
 
Now an important note if you still struggling is that when you switch-over to the right sub-tree, notice the imbalance at Node ‘a’, there is no left child, and similarly on the right Node ‘f’ has no left child. This could be the only real cause of confusion that may end you up with a different order.
Onto the meat, a peak into the code. Please note, the code is entirely my own and not aimed at being performant but through clear and clean code enable the reader to understand PreOrder Traversal.
Unit Test:
describe Trees::BinaryTree do
  before :each do
    @bst = Trees::BinaryTree.new('d') # set root

    # Left Subtree
    @bst.root.insert_left('b')
    @bst.root.left.insert_left('m')
    @bst.root.left.insert_right('k')
    @bst.root.left.right.insert_left('p')
    @bst.root.left.right.insert_right('t')

    # Right Subtree
    @bst.root.insert_right('c')

    @bst.root.right.insert_left('a')
    @bst.root.right.left.insert_right('g')

    @bst.root.right.insert_right('f')
    @bst.root.right.right.insert_right('h')

  end
  context 'traverse tree in specific order' do
    it 'should return values in preorder' do
      expect(@bst.preorder(@bst)).to eq ['d', 'b', 'm', 'k', 'p', 't', 'c', 'a', 'g', 'f', 'h']
    end
  end
end
Ruby Code:
module Trees
  class BinaryTree
    attr_reader :root

    class Node
      attr_reader :value, :left, :right

      def initialize(value)
        @value = value
        @left = nil
        @right = nil
      end

      def insert_left(value)
        @left = Node.new(value)
      end

      def insert_right(value)
        @right = Node.new(value)
      end
    end

    def initialize(root_value)
      @root = Node.new(root_value)
    end

    def preorder(node)
      result = []
      result << @root.value # start at root and add it's value
      result << preorder_subtree(node.root.left) # traverse left sub-tree
      result << preorder_subtree(node.root.right) # traverse right sub-tree
      result.flatten 
    end

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