Binary Tree Traversals

With implementation in C language using Borland C++ Builder 6.0

Discuss this article HERE

Introduction

Binary tree is a non-linear data structures consist of a finite set of nodes which either empty, or consist of a root and two disjoint binary trees, called the left and right sub-trees. While a tree must have at least one node, a binary tree may be empty. Likewise, a tree may have any number of sub-trees; a binary tree can have at most two.

Many algorithms pertaining to tree structures usually involve a process in which each node of the tree is “visited”, or processed, exactly once. Such a process is called a traversal. Three of such traversals are: preorder traversal, inorder traversal and postorder traversal. Binary tree traversals can be implemented recursively or non-recursively.

In this machine problem solution, the binary tree traversals was implemented using nonrecursive algorithm.

Problem Statement

Given a set of input representing the nodes of a binary tree, the program must be able to output the three traversal orders. The program must also capable of checking validity of the input, i.e., the program must know if the input is disjoint, duplicated and has a loop.

Problem Solution

    A. Binary Tree Traversals.
    The procedure to obtain the preorder, inorder, and postorder traversals are given below;
  1. Preorder traversal
    1. Visit the root
    2. Traverse the left sub-tree in preorder
    3. Traverse the right sub-tree in preorder
  2. Inorder traversal
    1. Traverse the left sub-tree in inorder
    2. Visit the root
    3. Traverse the right subtree in inorder
  3. Postorder traversal
    1. Traverse the left subtree in postorder
    2. Traverse the right subtree in postorder
    3. Visit the root
    B. Computer Implementation
    The tree traversal was implemented using non-recursive method. The algorithm is as follows;
  1. Preorder traversal
    1. define a stack
    2. traverse the left sub-tree and output each visited node while pushing it in on the stack until the leftmost node has been visited.
    3. If the right subtree is not null, pop the stack, then visit that sub-tree. Output that visited node while pushing it on the stack. If null, pop the stack.
    4. Do 2 and 3 until the stack is empty.
  2. Inorder traversal
    1. define a stack
    2. traverse the left sub-tree and push each visited node on the stack until the leftmost node has been visited.
    3. If the right sub-tree in not null, pop the stack and output it, then visit the right sub-tree and push it on the stack. If null, pop the stack and output it.
    4. Do 2 and 3 until the stack is empty.
  3. Postorder traversal
    1. define a stack
    2. traverse the left sub-tree and push each visited node on the stack until the leftmost node has been visited.
    3. If the right sub-tree in not null, visit the right sub-tree and push it on the stack. If null, pop the stack and output it.
    4. Do 2 and 3 until the stack is empty.
    C. Error Checking.
  1. The tree has a loop. The tree has a loop if;
    • The input left subtree or right subtree duplicates,
    • the input left subtree appear on the right subtree.
  2. The tree is not a binary tree. The tree is not a binary tree if;
    • The input root duplicates.
  3. The tree has a loop and it has no root. The tree has no root if;
    • the input has no leaf and does not terminate.
  4. The tree is disjoint. The tree is disjoint if;
    • the total number of input nodes is not equal to the nodes traversed.

Implementation


The algorithm was implemented in C programming Language using Borland C++ Builder 6.0 Development Environment . The program was tested on the example given on the specification and it outputs the same result. Various examples was also tested and outputs the correct traversal.

Conclusion

The binary tree traversal algorithm has been implemented using non-recursive procedure using the concept of the stack. The traversal can also be implemented using recursive procedure that will involve linked list.

From the above documentation of the algorithm, we had notice that there are some similarities among the three traversal algorithm that gave some ease of programming.

Downloads

To download the following files, point your mouse, "right click" then “Save Target As” for Internet Explorer or “Save Link As” for Mozila Firefox
miras.zip - Contains the source code in C language, stand alone executable file, and Full documentation

Sponsored Links