Binary Tree: PreOrder Traversal in Ruby

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

 

Leave a Reply

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