TheAlgorithms-C-Plus-Plus/others/iterative_tree_traversals.cpp

/**
 * @file
 * @brief Iterative version of Preorder, Postorder, and preorder [Traversal of
 * the Tree] (https://en.wikipedia.org/wiki/Tree_traversal)
 * @author [Motasim](https://github.com/motasimmakki)
 * @details
 *
 * ### 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.
 */
#include <algorithm>  /// for `reverse`
#include <cassert>    /// for `assert`
#include <iostream>   /// for I/O operations
#include <stack>      /// for `stack`
#include <vector>     /// for `vector`

/**
 * @namespace others
 * @brief Other algorithms
 */
namespace others {
/**
 * @namespace iterative_tree_traversals
 * @brief Functions for the [Traversal of the
 * Tree](https://en.wikipedia.org/wiki/Tree_traversal) algorithm
 */
namespace iterative_tree_traversals {
/**
 * @brief defines the structure of a node of the tree
 */
struct Node {
    int64_t data = 0;      ///< The value/key of the node.
    struct Node *left{};   ///< struct pointer to left subtree.
    struct Node *right{};  ///< struct pointer to right subtree.
};

/**
 * @brief defines the functions associated with the binary tree
 */
class BinaryTree {
 public:
    Node *createNewNode(
        int64_t);  ///< function that will create new node for insertion.
    std::vector<int64_t> preOrderIterative(
        Node *);  ///< function that takes root of the tree as an argument, and
                  ///< returns its preorder traversal.
    std::vector<int64_t> postOrderIterative(
        Node *);  ///< function that takes root of the tree as an argument, and
                  ///< returns its postorder traversal.
    std::vector<int64_t> inOrderIterative(
        Node *);  ///< function that takes root of the tree as an argument, and
                  ///< returns its inorder traversal.
};

/**
 * @brief will allocate the memory for a node and, along the data and return the
 * node.
 * @param data value that a particular node will contain.
 * @return pointer to the newly created node with assigned data.
 */
Node *BinaryTree::createNewNode(int64_t data) {
    Node *node = new Node();
    node->data = data;
    node->left = node->right = nullptr;
    return node;
}

/**
 * @brief preOrderIterative() function that will perform the preorder traversal
 * iteratively, and return the result array that contain the preorder traversal
 * of a tree.
 * @param root head/root node of a tree
 * @return result that is containing the preorder traversal of a tree
 */
std::vector<int64_t> BinaryTree::preOrderIterative(Node *root) {
    std::stack<Node *>
        stack;  ///< is used to find and traverse the child nodes.
    std::vector<int64_t> result;  ///< list of values, sorted in pre-order.

    stack.push(root);

    while (!stack.empty()) {
        result.push_back(stack.top()->data);
        Node *current = stack.top();
        stack.pop();

        if (current->right) {
            stack.push(current->right);
        }
        if (current->left) {
            stack.push(current->left);
        }
    }

    return result;
}

/**
 * @brief postOrderIterative() function that will perform the postorder
 * traversal iteratively, and return the result array that contain the postorder
 * traversal of a tree.
 * @param root head/root node of a tree
 * @return result that is containing the postorder traversal of a tree
 */
std::vector<int64_t> BinaryTree::postOrderIterative(Node *root) {
    std::stack<Node *>
        stack;  ///< is used to find and traverse the child nodes.
    std::vector<int64_t> result;  ///< List of values, sorted in post-order.

    stack.push(root);

    while (!stack.empty()) {
        result.push_back(stack.top()->data);
        Node *current = stack.top();
        stack.pop();

        if (current->left) {
            stack.push(current->left);
        }
        if (current->right) {
            stack.push(current->right);
        }
    }

    reverse(result.begin(), result.end());

    return result;
}

/**
 * @brief inOrderIterative() function that will perform the inorder traversal
 * iteratively, and return the result array that contain the inorder traversal
 * of a tree.
 * @param root head/root node of a tree
 * @return result that is containing the inorder traversal of a tree
 */
std::vector<int64_t> BinaryTree::inOrderIterative(Node *root) {
    std::stack<Node *>
        stack;  ///< is used to find and traverse the child nodes.
    std::vector<int64_t> result;  ///< List of values, sorted in in-order.

    Node *current = root;

    while (!stack.empty() || current) {
        while (current) {
            stack.push(current);
            current = current->left;
        }
        current = stack.top();
        stack.pop();
        result.push_back(current->data);
        current = current->right;
    }
    return result;
}
}  // namespace iterative_tree_traversals
}  // namespace others

/**
 * @brief Test the computed preorder with the actual preorder.
 * @param binaryTree instance of the BinaryTree class
 * @param root head/root node of a tree
 */
static void test1(others::iterative_tree_traversals::BinaryTree binaryTree,
                  others::iterative_tree_traversals::Node *root) {
    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 << "  ";
    }
}

/**
 * @brief Test the computed postorder with the actual postorder.
 * @param binaryTree instance of BinaryTree class
 * @param root head/root node of a tree
 */
static void test2(others::iterative_tree_traversals::BinaryTree binaryTree,
                  others::iterative_tree_traversals::Node *root) {
    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 << "  ";
    }
}

/**
 * @brief Test the computed inorder with the actual inorder.
 * @param binaryTree instance of BinaryTree class
 * @param root head/root node of a tree
 */
static void test3(others::iterative_tree_traversals::BinaryTree binaryTree,
                  others::iterative_tree_traversals::Node *root) {
    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 << "  ";
    }
}

/**
 * @brief Test the computed preorder with the actual preorder on negative value.
 * @param binaryTree instance of BinaryTree class
 * @param root head/root node of a tree
 */
static void test4(others::iterative_tree_traversals::BinaryTree binaryTree,
                  others::iterative_tree_traversals::Node *root) {
    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 << "  ";
    }
}

/**
 * @brief Test the computed postorder with the actual postorder on negative
 * value.
 * @param binaryTree instance of BinaryTree class
 * @param root head/root node of a tree
 */
static void test5(others::iterative_tree_traversals::BinaryTree binaryTree,
                  others::iterative_tree_traversals::Node *root) {
    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 << "  ";
    }
}

/**
 * @brief Test the computed inorder with the actual inorder on negative value.
 * @param binaryTree instance of BinaryTree class
 * @param root head/root node of a tree
 */
static void test6(others::iterative_tree_traversals::BinaryTree binaryTree,
                  others::iterative_tree_traversals::Node *root) {
    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 << "  ";
    }
}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    // 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;

    return 0;
}