Traversing Binary Trees

June 27, 2012
Revised: June 02, 2014

Code Baselined: December 03, 2002
Code Revised: June 13, 2012

Synopsis

I must have implemented linked list processing and/or stacks in almost every programming language I have had the opportunity to learn—scripting languages included. In this paper, both recursive and iterative binary tree algorithms are presented in the 4Test scripting language.


Introduction

My first exposure to computer science was in the Data Structures course I took at Monmouth College. The book for the course was The Art of Computer Programming: Volume 1 / Fundamental Algorithms which is sometimes affectionately referred to as Knuth Volume 1. Fortunately for us in the class, the professor skipped Chapter 1, Basic Concepts and went right into Chapter 2, Information Structures. During the course, I wrote all the assigned linked list and binary tree programming projects in IBM 360 Assembler.

Data are stored in singly linked lists as nodes made up of both a datum portion and a link portion. The link portion is a pointer to the next node in the list. The memory locations are not required to be sequential. When a new node is added to the list, the link in the last node is updated with a pointer to the next node in memory. Conversely, when a node is removed from the list, the deleted node or memory is returned to the free list and the link portion of the preceding node is updated with a pointer to the node which succeeded the deleted node—basically a pointer is swapped.

A binary tree is a special type of linked list. Nodes in a binary tree contain a datum portion, as in a singly linked list, but also contain both a left link and a right link. The left and right links are themselves pointers to new linked lists which are branches of the tree. Binary tree data structures are associated with efficient sorting and searching algorithms.

SilkTest Configuration

Whenever I develop scripts in SilkTest I normally create an options file (.opt) which is configured with a reference to an include file (.inc) that in turn contains references to all other include files required to support the 4Test script (.t). The Use Files parameter in the Runtime Options contains the entry Libs.inc as shown in Figure 1. The Libs.inc file contains a use statement for the additional include files: Algorithms.inc and Functions.inc. By using this technique only the Lib.inc file would need to be modified if new include files are added or existing ones deleted.

options_figure1
Figure 1

Libs.inc

 

The Algorithms

The Algorithms.inc file contains the code for the following binary tree algorithms:

  • Build_BTree
  • Traverse_BTree
  • NestedSet_BTree
  • ComputeDepth_BTree

Build_BTree

Build_BTree is a procedure which inserts nodes in a binary tree. For our purposes, the data structure used to implement the binary tree is an ARRAY[10][3] OF ANYTYPE. The procedure populates the array by reading items from a list and then assigning each item to an array element or node. Assignments are made based on whether the new value is less than or greater than the value in the node being examined. If the new value is less than the value in the examined node, then search the left branch. If the new value is greater than the value in the examined node, then search the right branch. Values are inserted until either the binary tree is full or the list is expended. Duplicates are discarded.

Traverse_BTree

Traverse_BTree is a procedure which performs recursive preorder, inorder or postorder traversals based on an input argument in the procedure call. The following traversal definitions in Table 1 are taken from Knuth Vol. 1, 2nd Edition page 316:

Table 1
Preorder traversal Inorder traversal Postorder traversal
Visit the root Traverse the left subtree Traverse the left subtree
Traverse the left subtree Visit the root Traverse the right subtree
Traverse the right subtree Traverse the right subtree Visit the root

NestedSet_BTree

NestedSet_BTree is a procedure which computes the nested set representation of a binary tree structure. The procedure is an implementation of Algorithm T from Knuth Vol. 1, page 317. For this paper, I converted the iterative algorithm from inorder to preorder and modified it slightly in order to implement the nested set computation.

ComputeDepth_BTree

ComputeDepth_BTree is a function which computes the depth of a binary tree. The depth of a binary tree is commonly defined as “The number of nodes along the longest path from the root node down to the farthest leaf node.” The maximum depth of an empty tree is 0.

Code Listing

 Supporting Functions & Procedures

The Functions.inc file contains the code for the functions and procedures:

  • ConvertListToCSV
  • ConvertCSVToList
  • Initialize_BTree
  • Print_BTree
  • Save_BTree
  • Load_BTree

ConvertListToCSV

ConvertListToCSV is a function which converts the binary tree to CSV format. This function is called by Save_BTree.

ConvertCSVToList

ConvertCSVToList is a function which converts the contents of a CSV file to a List. This function is called by Load_BTree.

Initialize_BTree

Initialize_BTree is a procedure which initializes the array representing the binary tree.

Print_BTree

Print_BTree is a procedure which dumps out the contents of the array representing the binary tree.

Save_BTree

Save_BTree is a procedure which writes the binary tree to a file in CSV format.

Load_BTree

Load_BTree is a procedure which retrieves the binary tree from a CSV file into a List.

Code Listing

 The Script

The BTree.t file is the 4Test script which manipulates the binary tree. The script exercises all the previously described procedures and functions.

Code Listing

 The Results

BTree.t script results are displayed below.

Click here for reuse options!
Copyright 2014 Gerard Sczepura

Leave a Reply

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