iterative_tree_traversals.cpp File Reference

Iterative version of Preorder, Postorder, and preorder [Traversal of the Tree] (https://en.wikipedia.org/wiki/Tree_traversal) More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stack>
#include <vector>

Include dependency graph for iterative_tree_traversals.cpp:

Classes
struct	others::iterative_tree_traversals::Node
	defines the structure of a node of the tree More...
class	others::iterative_tree_traversals::BinaryTree
	defines the functions associated with the binary tree More...

Namespaces
namespace	others
	for vector
namespace	iterative_tree_traversals
	Functions for the Traversal of the Tree algorithm.

Functions
void	others::iterative_tree_traversals::deleteAll (Node *root)
static void	test1 (others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node *root)
	Test the computed preorder with the actual preorder.
static void	test2 (others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node *root)
	Test the computed postorder with the actual postorder.
static void	test3 (others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node *root)
	Test the computed inorder with the actual inorder.
static void	test4 (others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node *root)
	Test the computed preorder with the actual preorder on negative value.
static void	test5 (others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node *root)
	Test the computed postorder with the actual postorder on negative value.
static void	test6 (others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node *root)
	Test the computed inorder with the actual inorder on negative value.
int	main ()
	Main function.

Detailed Description

Iterative version of Preorder, Postorder, and preorder [Traversal of the Tree] (https://en.wikipedia.org/wiki/Tree_traversal)

Author

Motasim

Iterative Preorder Traversal of a tree

Create a Stack that will store the Node of Tree. Push the root node into the stack. Save the root into the variabe named as current, and pop and elemnt from the stack. Store the data of current into the result array, and start traversing from it. Push both the child node of the current node into the stack, first right child then left child. Repeat the same set of steps untill the Stack becomes empty. And return the result array as the preorder traversal of a tree.

Iterative Postorder Traversal of a tree

Create a Stack that will store the Node of Tree. Push the root node into the stack. Save the root into the variabe named as current, and pop and elemnt from the stack. Store the data of current into the result array, and start traversing from it. Push both the child node of the current node into the stack, first left child then right child. Repeat the same set of steps untill the Stack becomes empty. Now reverse the result array and then return it to the calling function as a postorder traversal of a tree.

Iterative Inorder Traversal of a tree

Create a Stack that will store the Node of Tree. Push the root node into the stack. Save the root into the variabe named as current. Now iterate and take the current to the extreme left of the tree by traversing only to its left. Pop the elemnt from the stack and assign it to the current. Store the data of current into the result array. Repeat the same set of steps until the Stack becomes empty or the current becomes NULL. And return the result array as the inorder traversal of a tree.

Function Documentation

deleteAll()

void others::iterative_tree_traversals::deleteAll

(

Node *

root

)

                           {
    if (root) {
        std::stack<Node *> stack;
        stack.push(root);
 
        while (!stack.empty()) {
            const Node *current = stack.top();
            stack.pop();
 
            if (current->right) {
                stack.push(current->right);
            }
            if (current->left) {
                stack.push(current->left);
            }
            delete current;
        }
    }
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

< instace of BinaryTree, used to access its members functions.

           {
    // Creating a tree with the following structure,
    /*
              1
            /   \
           2     3
         /   \
        4     5
    */
 
    others::iterative_tree_traversals::BinaryTree
        binaryTree;  ///< instace of BinaryTree, used to access its members
                     ///< functions.
    others::iterative_tree_traversals::Node *root = binaryTree.createNewNode(1);
    root->left = binaryTree.createNewNode(2);
    root->right = binaryTree.createNewNode(3);
    root->left->left = binaryTree.createNewNode(4);
    root->left->right = binaryTree.createNewNode(5);
 
    std::cout << "\n| Tests for positive data value |" << std::endl;
    test1(binaryTree, root);  // run preorder-iterative test
    std::cout << "\nPre-order test Passed!" << std::endl;
 
    test2(binaryTree, root);  // run postorder-iterative test
    std::cout << "\nPost-order test Passed!" << std::endl;
 
    test3(binaryTree, root);  // run inorder-iterative test
    std::cout << "\nIn-order test Passed!" << std::endl;
 
    // Modifying tree for negative values.
    root->data = -1;
    root->left->data = -2;
    root->right->data = -3;
    root->left->left->data = -4;
    root->left->right->data = -5;
 
    std::cout << "\n| Tests for negative data values |" << std::endl;
    test4(binaryTree, root);  // run preorder-iterative test on negative values
    std::cout << "\nPre-order test on-negative value Passed!" << std::endl;
 
    test5(binaryTree, root);  // run postorder-iterative test on negative values
    std::cout << "\nPost-order test on-negative value Passed!" << std::endl;
 
    test6(binaryTree, root);  // run inorder-iterative test on negative values
    std::cout << "\nIn-order test on-negative value Passed!" << std::endl;
 
    deleteAll(root);
 
    return 0;
}

Here is the call graph for this function:

test1()

static void test1 ( others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node * root )

static

Test the computed preorder with the actual preorder.

Parameters

binaryTree	instance of the BinaryTree class
root	head/root node of a tree

< result stores the preorder traversal of the binary tree

                                                             {
    std::vector<int64_t> actual_result{1, 2, 4, 5, 3};
    std::vector<int64_t>
        result;  ///< result stores the preorder traversal of the binary tree
 
    // Calling preOrderIterative() function by passing a root node,
    // and storing the preorder traversal in result.
    result = binaryTree.preOrderIterative(root);
 
    // Self-testing the result using `assert`
    for (int i = 0; i < result.size(); i++) {
        assert(actual_result[i] == result[i]);
    }
 
    // Printing the result storing preorder.
    std::cout << "\nPreOrder Traversal Is : " << std::endl;
    for (auto i : result) {
        std::cout << i << "  ";
    }
}

Here is the call graph for this function:

test2()

static void test2 ( others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node * root )

static

Test the computed postorder with the actual postorder.

Parameters

binaryTree	instance of BinaryTree class
root	head/root node of a tree

< result stores the postorder traversal of the binary tree.

                                                             {
    std::vector<int64_t> actual_result{4, 5, 2, 3, 1};
    std::vector<int64_t>
        result;  ///< result stores the postorder traversal of the binary tree.
 
    // Calling postOrderIterative() function by passing a root node,
    // and storing the postorder traversal in result.
    result = binaryTree.postOrderIterative(root);
 
    // Self-testing the result using `assert`
    for (int i = 0; i < result.size(); i++) {
        assert(actual_result[i] == result[i]);
    }
 
    // Printing the result storing postorder.
    std::cout << "\nPostOrder Traversal Is : " << std::endl;
    for (auto i : result) {
        std::cout << i << "  ";
    }
}

Here is the call graph for this function:

test3()

static void test3 ( others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node * root )

static

Test the computed inorder with the actual inorder.

Parameters

binaryTree	instance of BinaryTree class
root	head/root node of a tree

< result stores the inorder traversal of the binary tree.

                                                             {
    std::vector<int64_t> actual_result{4, 2, 5, 1, 3};
    std::vector<int64_t>
        result;  ///< result stores the inorder traversal of the binary tree.
 
    // Calling inOrderIterative() function by passing a root node,
    // and storing the inorder traversal in result.
    result = binaryTree.inOrderIterative(root);
 
    // Self-testing the result using `assert`
    for (int i = 0; i < result.size(); i++) {
        assert(actual_result[i] == result[i]);
    }
 
    // Printing the result storing inorder.
    std::cout << "\nInOrder Traversal Is : " << std::endl;
    for (auto i : result) {
        std::cout << i << "  ";
    }
}

Here is the call graph for this function:

test4()

static void test4 ( others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node * root )

static

Test the computed preorder with the actual preorder on negative value.

Parameters

binaryTree	instance of BinaryTree class
root	head/root node of a tree

< result stores the preorder traversal of the binary tree

                                                             {
    std::vector<int64_t> actual_result{-1, -2, -4, -5, -3};
    std::vector<int64_t>
        result;  ///< result stores the preorder traversal of the binary tree
 
    // Calling preOrderIterative() function by passing a root node,
    // and storing the preorder traversal in result.
    result = binaryTree.preOrderIterative(root);
 
    // Self-testing the result using `assert`
    for (int i = 0; i < result.size(); i++) {
        assert(actual_result[i] == result[i]);
    }
 
    // Printing the result storing preorder.
    std::cout << "\nPreOrder Traversal Is : " << std::endl;
    for (auto i : result) {
        std::cout << i << "  ";
    }
}

Here is the call graph for this function:

test5()

static void test5 ( others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node * root )

static

Test the computed postorder with the actual postorder on negative value.

Parameters

binaryTree	instance of BinaryTree class
root	head/root node of a tree

< result stores the postorder traversal of the binary tree.

                                                             {
    std::vector<int64_t> actual_result{-4, -5, -2, -3, -1};
    std::vector<int64_t>
        result;  ///< result stores the postorder traversal of the binary tree.
 
    // Calling postOrderIterative() function by passing a root node,
    // and storing the postorder traversal in result.
    result = binaryTree.postOrderIterative(root);
 
    // Self-testing the result using `assert`
    for (int i = 0; i < result.size(); i++) {
        assert(actual_result[i] == result[i]);
    }
 
    // Printing the result storing postorder.
    std::cout << "\nPostOrder Traversal Is : " << std::endl;
    for (auto i : result) {
        std::cout << i << "  ";
    }
}

Here is the call graph for this function:

test6()

static void test6 ( others::iterative_tree_traversals::BinaryTree binaryTree, others::iterative_tree_traversals::Node * root )

static

Test the computed inorder with the actual inorder on negative value.

Parameters

binaryTree	instance of BinaryTree class
root	head/root node of a tree

< result stores the inorder traversal of the binary tree.

                                                             {
    std::vector<int64_t> actual_result{-4, -2, -5, -1, -3};
    std::vector<int64_t>
        result;  ///< result stores the inorder traversal of the binary tree.
 
    // Calling inOrderIterative() function by passing a root node,
    // and storing the inorder traversal in result.
    result = binaryTree.inOrderIterative(root);
 
    // Self-testing the result using `assert`
    for (int i = 0; i < result.size(); i++) {
        assert(actual_result[i] == result[i]);
    }
 
    // Printing the result storing inorder.
    std::cout << "\nInOrder Traversal Is : " << std::endl;
    for (auto i : result) {
        std::cout << i << "  ";
    }
}

Here is the call graph for this function: