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:**

*Display value of root*
*Traverse the left tree *
*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

** **

*Related*