Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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)
183 {
184 if (root) {
186 stack.push(root);
187
188 while (!stack.empty()) {
189 const Node *current = stack.top();
190 stack.pop();
191
192 if (current->right) {
193 stack.push(current->right);
194 }
195 if (current->left) {
196 stack.push(current->left);
197 }
198 delete current;
199 }
200 }
201}
for std::invalid_argument
Definition stack.hpp:19
void pop()
Definition stack.hpp:62
void push(const value_type &item)
Definition stack.hpp:47
value_type top() const
Definition stack.hpp:56
char stack[MAX]
Definition paranthesis_matching.cpp:20
Definition linkedlist_implentation_usingarray.cpp:14

◆ main()

int main ( void )

Main function.

Returns
0 on exit

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

372 {
373 // Creating a tree with the following structure,
374 /*
375 1
376 / \
377 2 3
378 / \
379 4 5
380 */
381
383 binaryTree; ///< instace of BinaryTree, used to access its members
384 ///< functions.
386 root->left = binaryTree.createNewNode(2);
387 root->right = binaryTree.createNewNode(3);
388 root->left->left = binaryTree.createNewNode(4);
389 root->left->right = binaryTree.createNewNode(5);
390
391 std::cout << "\n| Tests for positive data value |" << std::endl;
392 test1(binaryTree, root); // run preorder-iterative test
393 std::cout << "\nPre-order test Passed!" << std::endl;
394
395 test2(binaryTree, root); // run postorder-iterative test
396 std::cout << "\nPost-order test Passed!" << std::endl;
397
398 test3(binaryTree, root); // run inorder-iterative test
399 std::cout << "\nIn-order test Passed!" << std::endl;
400
401 // Modifying tree for negative values.
402 root->data = -1;
403 root->left->data = -2;
404 root->right->data = -3;
405 root->left->left->data = -4;
406 root->left->right->data = -5;
407
408 std::cout << "\n| Tests for negative data values |" << std::endl;
409 test4(binaryTree, root); // run preorder-iterative test on negative values
410 std::cout << "\nPre-order test on-negative value Passed!" << std::endl;
411
412 test5(binaryTree, root); // run postorder-iterative test on negative values
413 std::cout << "\nPost-order test on-negative value Passed!" << std::endl;
414
415 test6(binaryTree, root); // run inorder-iterative test on negative values
416 std::cout << "\nIn-order test on-negative value Passed!" << std::endl;
417
418 deleteAll(root);
419
420 return 0;
421}
defines the functions associated with the binary tree
Definition iterative_tree_traversals.cpp:67
Node * createNewNode(int64_t)
function that will create new node for insertion.
Definition iterative_tree_traversals.cpp:88
static void test2()
Self-implementations, 2nd test.
Definition dsu_path_compression.cpp:186
static void test1()
Self-test implementations, 1st test.
Definition dsu_path_compression.cpp:169
T endl(T... args)
static void test3()
Definition hamiltons_cycle.cpp:122
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.
Definition iterative_tree_traversals.cpp:291
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.
Definition iterative_tree_traversals.cpp:319
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.
Definition iterative_tree_traversals.cpp:346
defines the structure of a node of the tree
Definition iterative_tree_traversals.cpp:58
Here is the call graph for this function:

◆ test1()

Test the computed preorder with the actual preorder.

Parameters
binaryTreeinstance of the BinaryTree class
roothead/root node of a tree

< result stores the preorder traversal of the binary tree

211 {
212 std::vector<int64_t> actual_result{1, 2, 4, 5, 3};
214 result; ///< result stores the preorder traversal of the binary tree
215
216 // Calling preOrderIterative() function by passing a root node,
217 // and storing the preorder traversal in result.
218 result = binaryTree.preOrderIterative(root);
219
220 // Self-testing the result using `assert`
221 for (int i = 0; i < result.size(); i++) {
222 assert(actual_result[i] == result[i]);
223 }
224
225 // Printing the result storing preorder.
226 std::cout << "\nPreOrder Traversal Is : " << std::endl;
227 for (auto i : result) {
228 std::cout << i << " ";
229 }
230}
std::vector< int64_t > preOrderIterative(Node *)
preOrderIterative() function that will perform the preorder traversal iteratively,...
Definition iterative_tree_traversals.cpp:102
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:76
Here is the call graph for this function:

◆ test2()

Test the computed postorder with the actual postorder.

Parameters
binaryTreeinstance of BinaryTree class
roothead/root node of a tree

< result stores the postorder traversal of the binary tree.

238 {
239 std::vector<int64_t> actual_result{4, 5, 2, 3, 1};
241 result; ///< result stores the postorder traversal of the binary tree.
242
243 // Calling postOrderIterative() function by passing a root node,
244 // and storing the postorder traversal in result.
245 result = binaryTree.postOrderIterative(root);
246
247 // Self-testing the result using `assert`
248 for (int i = 0; i < result.size(); i++) {
249 assert(actual_result[i] == result[i]);
250 }
251
252 // Printing the result storing postorder.
253 std::cout << "\nPostOrder Traversal Is : " << std::endl;
254 for (auto i : result) {
255 std::cout << i << " ";
256 }
257}
std::vector< int64_t > postOrderIterative(Node *)
postOrderIterative() function that will perform the postorder traversal iteratively,...
Definition iterative_tree_traversals.cpp:132
Here is the call graph for this function:

◆ test3()

Test the computed inorder with the actual inorder.

Parameters
binaryTreeinstance of BinaryTree class
roothead/root node of a tree

< result stores the inorder traversal of the binary tree.

265 {
266 std::vector<int64_t> actual_result{4, 2, 5, 1, 3};
268 result; ///< result stores the inorder traversal of the binary tree.
269
270 // Calling inOrderIterative() function by passing a root node,
271 // and storing the inorder traversal in result.
272 result = binaryTree.inOrderIterative(root);
273
274 // Self-testing the result using `assert`
275 for (int i = 0; i < result.size(); i++) {
276 assert(actual_result[i] == result[i]);
277 }
278
279 // Printing the result storing inorder.
280 std::cout << "\nInOrder Traversal Is : " << std::endl;
281 for (auto i : result) {
282 std::cout << i << " ";
283 }
284}
std::vector< int64_t > inOrderIterative(Node *)
inOrderIterative() function that will perform the inorder traversal iteratively, and return the resul...
Definition iterative_tree_traversals.cpp:164
Here is the call graph for this function:

◆ test4()

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

Parameters
binaryTreeinstance of BinaryTree class
roothead/root node of a tree

< result stores the preorder traversal of the binary tree

292 {
293 std::vector<int64_t> actual_result{-1, -2, -4, -5, -3};
295 result; ///< result stores the preorder traversal of the binary tree
296
297 // Calling preOrderIterative() function by passing a root node,
298 // and storing the preorder traversal in result.
299 result = binaryTree.preOrderIterative(root);
300
301 // Self-testing the result using `assert`
302 for (int i = 0; i < result.size(); i++) {
303 assert(actual_result[i] == result[i]);
304 }
305
306 // Printing the result storing preorder.
307 std::cout << "\nPreOrder Traversal Is : " << std::endl;
308 for (auto i : result) {
309 std::cout << i << " ";
310 }
311}
Here is the call graph for this function:

◆ test5()

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

Parameters
binaryTreeinstance of BinaryTree class
roothead/root node of a tree

< result stores the postorder traversal of the binary tree.

320 {
321 std::vector<int64_t> actual_result{-4, -5, -2, -3, -1};
323 result; ///< result stores the postorder traversal of the binary tree.
324
325 // Calling postOrderIterative() function by passing a root node,
326 // and storing the postorder traversal in result.
327 result = binaryTree.postOrderIterative(root);
328
329 // Self-testing the result using `assert`
330 for (int i = 0; i < result.size(); i++) {
331 assert(actual_result[i] == result[i]);
332 }
333
334 // Printing the result storing postorder.
335 std::cout << "\nPostOrder Traversal Is : " << std::endl;
336 for (auto i : result) {
337 std::cout << i << " ";
338 }
339}
Here is the call graph for this function:

◆ test6()

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

Parameters
binaryTreeinstance of BinaryTree class
roothead/root node of a tree

< result stores the inorder traversal of the binary tree.

347 {
348 std::vector<int64_t> actual_result{-4, -2, -5, -1, -3};
350 result; ///< result stores the inorder traversal of the binary tree.
351
352 // Calling inOrderIterative() function by passing a root node,
353 // and storing the inorder traversal in result.
354 result = binaryTree.inOrderIterative(root);
355
356 // Self-testing the result using `assert`
357 for (int i = 0; i < result.size(); i++) {
358 assert(actual_result[i] == result[i]);
359 }
360
361 // Printing the result storing inorder.
362 std::cout << "\nInOrder Traversal Is : " << std::endl;
363 for (auto i : result) {
364 std::cout << i << " ";
365 }
366}
Here is the call graph for this function: