recursive_tree_traversal.cpp File Reference

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

#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for recursive_tree_traversal.cpp:

Classes
struct	others::recursive_tree_traversals::Node
	The structure to hold Nodes of the tree. More...
class	others::recursive_tree_traversals::BT
	BT used to make the entire structure of the binary tree and the functions associated with the binary tree. More...

Namespaces
namespace	others
	for vector
namespace	interpolation_search
	Functions for the Recursive version of Inorder, Preorder, and Postorder Traversal of the Tree algorithm implementation.

Functions
void	test1 ()
	1st test-case
void	test2 ()
	2nd test-case
void	test3 ()
	3rd test-case
static void	tests ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

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

Iterative Inorder Traversal of a tree

For traversing a (non-empty) binary tree in an inorder fashion, we must do these three things for every node n starting from the tree’s root:

(L) Recursively traverse its left subtree. When this step is finished, we are back at n again. (N) Process n itself. (R) Recursively traverse its right subtree. When this step is finished, we are back at n again.

In normal inorder traversal, we visit the left subtree before the right subtree. If we visit the right subtree before visiting the left subtree, it is referred to as reverse inorder traversal.

Iterative Preorder Traversal of a tree

For traversing a (non-empty) binary tree in a preorder fashion, we must do these three things for every node n starting from the tree’s root:

(N) Process n itself. (L) Recursively traverse its left subtree. When this step is finished, we are back at n again. (R) Recursively traverse its right subtree. When this step is finished, we are back at n again.

In normal preorder traversal, visit the left subtree before the right subtree. If we visit the right subtree before visiting the left subtree, it is referred to as reverse preorder traversal.

Iterative Postorder Traversal of a tree

For traversing a (non-empty) binary tree in a postorder fashion, we must do these three things for every node n starting from the tree’s root:

(L) Recursively traverse its left subtree. When this step is finished, we are back at n again. (R) Recursively traverse its right subtree. When this step is finished, we are back at n again. (N) Process n itself.

In normal postorder traversal, visit the left subtree before the right subtree. If we visit the right subtree before visiting the left subtree, it is referred to as reverse postorder traversal.

Author

Lajat Manekar

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    tests();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test1()

void test1

(

)

1st test-case

Returns

void

< result stores the inorder traversal of the binary tree

< result stores the preorder traversal of the binary tree

< result stores the postorder traversal of the binary tree

             {
    others::recursive_tree_traversals::BT obj1;
    others::recursive_tree_traversals::Node *root = obj1.createNewNode(2);
    root->left = obj1.createNewNode(7);
    root->right = obj1.createNewNode(5);
    root->left->left = obj1.createNewNode(2);
    root->left->right = obj1.createNewNode(6);
    root->right->right = obj1.createNewNode(9);
    root->left->right->left = obj1.createNewNode(5);
    root->left->right->right = obj1.createNewNode(11);
    root->right->right->left = obj1.createNewNode(4);
 
    std::vector<uint64_t> actual_result_inorder{2, 7, 5, 6, 11, 2, 5, 4, 9};
    std::vector<uint64_t> actual_result_preorder{2, 7, 2, 6, 5, 11, 5, 9, 4};
    std::vector<uint64_t> actual_result_postorder{2, 5, 11, 6, 7, 4, 9, 5, 2};
    std::vector<uint64_t> result_inorder;    ///< result stores the inorder
                                             ///< traversal of the binary tree
    std::vector<uint64_t> result_preorder;   ///< result stores the preorder
                                             ///< traversal of the binary tree
    std::vector<uint64_t> result_postorder;  ///< result stores the postorder
                                             ///< traversal of the binary tree
 
    uint64_t size = actual_result_inorder.size();
 
    // Calling inorder() function by passing a root node,
    // and storing the inorder traversal in result_inorder.
    result_inorder = obj1.inorder(root);
    std::cout << "Testcase #1: Inorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_inorder[i] == result_inorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    // Calling preorder() function by passing a root node,
    // and storing the preorder traversal in result_preorder.
    result_preorder = obj1.preorder(root);
    std::cout << "Testcase #1: Preorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_preorder[i] == result_preorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    // Calling postorder() function by passing a root node,
    // and storing the postorder traversal in result_postorder.
    result_postorder = obj1.postorder(root);
    std::cout << "Testcase #1: Postorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_postorder[i] == result_postorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    std::cout << std::endl;
}

Here is the call graph for this function:

test2()

void test2

(

)

2nd test-case

Returns

void

< result stores the inorder traversal of the binary tree

< result stores the preorder traversal of the binary tree

< result stores the postorder traversal of the binary tree

             {
    others::recursive_tree_traversals::BT obj2;
    others::recursive_tree_traversals::Node *root = obj2.createNewNode(1);
    root->left = obj2.createNewNode(2);
    root->right = obj2.createNewNode(3);
    root->left->left = obj2.createNewNode(4);
    root->right->left = obj2.createNewNode(5);
    root->right->right = obj2.createNewNode(6);
    root->right->left->left = obj2.createNewNode(7);
    root->right->left->right = obj2.createNewNode(8);
 
    std::vector<uint64_t> actual_result_inorder{4, 2, 1, 7, 5, 8, 3, 6};
    std::vector<uint64_t> actual_result_preorder{1, 2, 4, 3, 5, 7, 8, 6};
    std::vector<uint64_t> actual_result_postorder{4, 2, 7, 8, 5, 6, 3, 1};
    std::vector<uint64_t> result_inorder;    ///< result stores the inorder
                                             ///< traversal of the binary tree
    std::vector<uint64_t> result_preorder;   ///< result stores the preorder
                                             ///< traversal of the binary tree
    std::vector<uint64_t> result_postorder;  ///< result stores the postorder
                                             ///< traversal of the binary tree
 
    uint64_t size = actual_result_inorder.size();
 
    // Calling inorder() function by passing a root node,
    // and storing the inorder traversal in result_inorder.
    result_inorder = obj2.inorder(root);
    std::cout << "Testcase #2: Inorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_inorder[i] == result_inorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    // Calling preorder() function by passing a root node,
    // and storing the preorder traversal in result_preorder.
    result_preorder = obj2.preorder(root);
    std::cout << "Testcase #2: Preorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_preorder[i] == result_preorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    // Calling postorder() function by passing a root node,
    // and storing the postorder traversal in result_postorder.
    result_postorder = obj2.postorder(root);
    std::cout << "Testcase #2: Postorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_postorder[i] == result_postorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    std::cout << std::endl;
}

Here is the call graph for this function:

test3()

void test3

(

)

3rd test-case

Returns

void

< result stores the inorder traversal of the binary tree

< result stores the preorder traversal of the binary tree

< result stores the postorder traversal of the binary tree

             {
    others::recursive_tree_traversals::BT obj3;
    others::recursive_tree_traversals::Node *root = obj3.createNewNode(1);
    root->left = obj3.createNewNode(2);
    root->right = obj3.createNewNode(3);
    root->left->left = obj3.createNewNode(4);
    root->left->right = obj3.createNewNode(5);
 
    std::vector<uint64_t> actual_result_inorder{4, 2, 5, 1, 3};
    std::vector<uint64_t> actual_result_preorder{1, 2, 4, 5, 3};
    std::vector<uint64_t> actual_result_postorder{4, 5, 2, 3, 1};
    std::vector<uint64_t> result_inorder;    ///< result stores the inorder
                                             ///< traversal of the binary tree
    std::vector<uint64_t> result_preorder;   ///< result stores the preorder
                                             ///< traversal of the binary tree
    std::vector<uint64_t> result_postorder;  ///< result stores the postorder
                                             ///< traversal of the binary tree
 
    uint64_t size = actual_result_inorder.size();
 
    // Calling inorder() function by passing a root node,
    // and storing the inorder traversal in result_inorder.
 
    result_inorder = obj3.inorder(root);
    std::cout << "Testcase #3: Inorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_inorder[i] == result_inorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    // Calling preorder() function by passing a root node,
    // and storing the preorder traversal in result_preorder.
    result_preorder = obj3.preorder(root);
    std::cout << "Testcase #3: Preorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_preorder[i] == result_preorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    // Calling postorder() function by passing a root node,
    // and storing the postorder traversal in result_postorder.
    result_postorder = obj3.postorder(root);
    std::cout << "Testcase #3: Postorder Traversal...";
    for (auto i = 0; i < size; ++i) {
        assert(actual_result_postorder[i] == result_postorder[i]);
    }
    std::cout << "Passed!" << std::endl;
 
    std::cout << std::endl;
}

Here is the call graph for this function:

tests()

static void tests ( )

static

Self-test implementations.

Returns

void

                    {
    std::cout << "1st test-case" << std::endl;
    test1();  // run 1st test-case
    std::cout << "2nd test-case" << std::endl;
    test2();  // run 2nd test-case
    std::cout << "3rd test-case" << std::endl;
    test3();  // run 3rd test-case
}

Here is the call graph for this function: