Transversing Binary Trees

Binary trees are a data structure that I first encountered in a Turbo Pascal course. Later encounters with trees, not necessarily binary in nature, involved primitive text file compression. Binary means having two of something. Binary numbers have one of two values: 0 or 1. Binary trees can have up to two children, a left and a right child. Like Tarzan swinging from vine to vine, there are different ways to leap from one node to another on a binary tree. Well, there are three different ways: preorder, inorder, and postorder transversals.

We will need a binary tree to work with. In my explanations below, I’ll use the following binary tree, referring to the circles with numbers in them as nodes. For example, node 5 is the topmost circle or the root of the binary tree. The two trees with children are outlined as Tree 1 and Tree 2 for easier explanation.

All three transversals explore the left subtree followed by the right subtree. However, the order in which the current node is display differs in each transversal.

Preorder. I’ll start with a preorder transversal first which is also known as a depth first transversal, charting the descent to the depths of the binary tree. The preorder transversal displays the contents of the current node prior to transversing any children. Each time that a new node is visited, the steps of the algorithm start from the beginning.

Display this node.
Visit the left child, transversing that tree.
Visit the right child, transversing that tree.

The transversal begins at the root of the tree, node 5.

1. Display node 5

Tree 2:

1. We haven’t visited the left child. Go left to node 10.
2. Display node 10.
3. We haven’t visited the left child. Display node 20.
4. At node 20, we can neither go left nor right. Climb up to node 10.
5. We haven’t visited the right child. Display node 25.
6. Climb up to node 10.

Tree 1:

1. Since we’ve visited both children at node 10, climb up to node 5.
2. We haven’t visited the right child. Display node 15.

The output of the preorder transversal would be: 5, 10, 20, 25, 15.

Inorder. The inorder transversal explores the left subtree, prior to display the current node. Then, the right subtree is explored.

Visit the left child, transversing that tree.
Display this node.
Visit the right child, transversing that tree.

The transversal begins at node 5.

1. We haven’t visited the left child. Go left to node 10.

Tree 2:

1. We haven’t visited the left child. Go left to node 20.
2. At node 20, we can neither go left nor right. Display node 20.
3. Climb up to node 10.
4. We already been to the left child. Display node 10.
5. We haven’t visited the right child. Go right to node 25.
6. At node 25, we’ve reached another leaf (childless) node. Display node 25.
7. Climb up to node 10.

Tree 1:

1. Climb up to node 5.
2. Since we’ve already visited the left child, display node 5.
3. We have not go to the right child. Go right to node 15.
4. Display node 15.

The output of the preorder transversal would be: 20, 10, 25, 5, 15.

Postorder. This is the easiest to conceptualize for me. You transverse the left subtree, transverse the right subtree, and then display the current node’s value.

Visit the left child, transversing that tree.
Visit the right child, transversing that tree.
Display this node.

Using the example above, the transversal begins at node 5.

1. We haven’t visited the left child. Go left to node 10.

Enter Tree 2:

1. We haven’t visited the left child. Go left to node 20.
2. At node 20 we can’t go left nor right. Display node 20.
3. Climb up to node 10, go right to node 25.
4. At node 25 we can’t go left nor right. Display node 25.
5. Climb up to node 10. We’ve already visited both children. Display node 10.

Enter Tree 1:

1. Climb up to node 5.
2. We’ve visited the child to the left of node 5, but we haven’t visited node 15. Go right to node 15.
3. At node 15 we can’t go left or right. Display node 15.
4. Climb up to node 5.
5. We’ve visited both children. Display node 5.

The output of this transversal would be: 20, 25, 10, 15, 5.

Now, that the dry explanation is done, it’s time to dust-off some of the Ruby code that I’ve written last year.

First, we have an implementation of a binary tree node. The object has the ability to hold a node value, a left node, and a right child.

File: BinaryTreeNode.rb

# This is an implementation of a binary tree node,
# a primitive data structure.
class BinaryTreeNode
  attr_writer :value, :left, :right
  attr_reader :value, :left, :right

  # Constructor for a BinaryTreeNode
  #
  # [value] The value of the node
  # [left] The left child node.
  # [right] The right child node.
  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end

  # Display the value of the node.
  def to_s
    return @value
  end

  # Determines if a left child exists.
  def hasLeft
    has_left = false

    if (@left != nil) then
      has_left = true
    end
  end

  # Determines if a right child exists.
  def hasRight
    has_right = false

    if (@right != nil) then
      has_right = true
    end
  end

  # Determines if this node has no children.
  def isLeaf
    is_leaf = false

    if ((@left == nil) && (@right == nil)) then
      is_leaf = true
    end

    return is_leaf
  end
end

Next, here’s the class that transverses the binary tree. It has the ability to do preorder, inorder, and postorder transversals.

File: BinaryTreeTransverser.rb

require('BinaryTreeNode')

# Responsible for transversing a binary tree
class BinaryTreeTransverser

  # Follows a recursive preorder transveral
  # [node] The node to begin the transversal
  # [transveralArray] An array of node values transversed
  def preorder(node, transversalArray)
    transversalArray.push(node.to_s)

    if (node.hasLeft) then
      preorder(node.left, transversalArray)
    end

    if (node.hasRight) then
      preorder(node.right, transversalArray)
    end
  end

  # Follows a recursive inorder transveral
  # [node] The node to begin the transversal
  # [transveralArray] An array of node values transversed
  def inorder(node, transversalArray)
    if (node.hasLeft) then
      inorder(node.left, transversalArray)
    end

    transversalArray.push(node.to_s)

    if (node.hasRight) then
      inorder(node.right, transversalArray)
    end
  end

  # Follows a recursive postorder transversal
  # [node] The node to begin the transversal
  # [transveralArray] An array of node values transversed
  def postorder(node, transversalArray)
    if (node.hasLeft) then
      postorder(node.left, transversalArray)
    end

    if (node.hasRight) then
      postorder(node.right, transversalArray)
    end

    transversalArray.push(node.to_s)
  end

end

Finally, here are the unit test cases ensuring that each transversal operates correctly. As it turns out, I didn’t assemble the test tree correctly, leading to the unit tests not passing.

File: BinaryTreeTransverserTest.rb

require 'test/unit'
require 'BinaryTreeNode'
require 'BinaryTreeTransverser'

# Tests pre, post, and inorder binary tree transversals
class BinaryTreeTransverserTest < Test::Unit::TestCase

  # Creates a binary tree to test with
  def setup
    @test_tree = nil;

    # Time to practice my ASCII art skills.
    # The first four trees will be the legs of our tree.
    #
    #     A
    #   /   \
    #  5     8
    leftLeaf = BinaryTreeNode.new(5, nil, nil)
    rightLeaf = BinaryTreeNode.new(8, nil, nil)
    nodeA = BinaryTreeNode.new('A', leftLeaf, rightLeaf)

    #     B
    #   /
    #  20
    leftLeaf = BinaryTreeNode.new(20, nil, nil)
    nodeB = BinaryTreeNode.new('B', leftLeaf, nil)

    #     C
    #      \
    #       4
    rightLeaf = BinaryTreeNode.new(4, nil, nil)
    nodeC = BinaryTreeNode.new('C', nil, rightLeaf)

    #     D
    #   /   \
    #  12    42
    leftLeaf = BinaryTreeNode.new(12, nil, nil)
    rightLeaf = BinaryTreeNode.new(42, nil, nil)
    nodeD = BinaryTreeNode.new('D', leftLeaf, rightLeaf)

    # Constructs the rest of the tree.
    #
    #                       R
    #                     /   \
    #                  L         M
    #                /  \      /
    #              Z     X    W
    #             / \   / \
    #            A   B C   D
    #           /|  /   \  | \
    #          5 8 20    4 12 42
    nodeZ = BinaryTreeNode.new('Z', nodeA, nodeB)
    nodeX = BinaryTreeNode.new('X', nodeC, nodeD)
    nodeW = BinaryTreeNode.new('W', nil, nil)
    nodeL = BinaryTreeNode.new('L', nodeZ, nodeX)
    nodeM = BinaryTreeNode.new('M', nodeW, nil)

    # The root node of the tree which all test case
    # will test against
    @rootNode = BinaryTreeNode.new('R', nodeL, nodeM)
  end

  # Tests a preorder transveral
  def testPreorder
    correctPreorder = ['R', 'L', 'Z', 'A', 5, 8, 'B', 20, 'X', 'C', 4, 'D', 12, 42, 'M', 'W']
    testTransversal = Array.new
    BinaryTreeTransverser.new.preorder(@rootNode, testTransversal) 

    assert_equal(correctPreorder, testTransversal)
  end

  # Tests an inorder transversal
  def testInorder
    correctPreorder = [5, 'A', 8, 'Z', 20, 'B', 'L', 'C', 4, 'X', 12, 'D', 42, 'R', 'W', 'M']
    testTransversal = Array.new
    BinaryTreeTransverser.new.inorder(@rootNode, testTransversal)

    assert_equal(correctPreorder, testTransversal)
  end

  # Tests a postorder transversal
  def testPostorder
    correctPostorder = [5, 8, 'A', 20, 'B', 'Z', 4, 'C', 12, 42, 'D', 'X', 'L', 'W', 'M', 'R']
    testTransversal = Array.new
    BinaryTreeTransverser.new.postorder(@rootNode, testTransversal)

    assert_equal(correctPostorder, testTransversal)
  end

end