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 <cstdint>
#include <iostream>
#include <vector>

Include dependency graph for recursive_tree_traversal.cpp:

Go to the source code of this file.

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	others::recursive_tree_traversals::deleteAll (const Node *const root)
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

Definition in file recursive_tree_traversal.cpp.

Function Documentation

deleteAll()

void others::recursive_tree_traversals::deleteAll

(

const Node *const

root

)

Definition at line 185 of file recursive_tree_traversal.cpp.

                                       {
    if (root) {
        deleteAll(root->left);
        deleteAll(root->right);
        delete root;
    }
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 398 of file recursive_tree_traversal.cpp.

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

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

Definition at line 201 of file recursive_tree_traversal.cpp.

             {
    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<std::uint64_t> actual_result_inorder{2, 7, 5, 6, 11,
                                                     2, 5, 4, 9};
    std::vector<std::uint64_t> actual_result_preorder{2,  7, 2, 6, 5,
                                                      11, 5, 9, 4};
    std::vector<std::uint64_t> actual_result_postorder{2, 5, 11, 6, 7,
                                                       4, 9, 5,  2};
    std::vector<std::uint64_t>
        result_inorder;  
    std::vector<std::uint64_t>
        result_preorder;  
    std::vector<std::uint64_t>
        result_postorder;  
 
    std::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;
    deleteAll(root);
}

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

Definition at line 266 of file recursive_tree_traversal.cpp.

             {
    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<std::uint64_t> actual_result_inorder{4, 2, 1, 7, 5, 8, 3, 6};
    std::vector<std::uint64_t> actual_result_preorder{1, 2, 4, 3, 5, 7, 8, 6};
    std::vector<std::uint64_t> actual_result_postorder{4, 2, 7, 8, 5, 6, 3, 1};
    std::vector<std::uint64_t>
        result_inorder;  
    std::vector<std::uint64_t>
        result_preorder;  
    std::vector<std::uint64_t>
        result_postorder;  
 
    std::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;
    deleteAll(root);
}

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

Definition at line 327 of file recursive_tree_traversal.cpp.

             {
    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<std::uint64_t> actual_result_inorder{4, 2, 5, 1, 3};
    std::vector<std::uint64_t> actual_result_preorder{1, 2, 4, 5, 3};
    std::vector<std::uint64_t> actual_result_postorder{4, 5, 2, 3, 1};
    std::vector<std::uint64_t>
        result_inorder;  
    std::vector<std::uint64_t>
        result_preorder;  
    std::vector<std::uint64_t>
        result_postorder;  
 
    std::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;
    deleteAll(root);
}

tests()

static void tests ( )

static

Self-test implementations.

Returns

void

Definition at line 386 of file recursive_tree_traversal.cpp.

                    {
    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
}