Non-recursive implementation of binary tree traversals, Data Structure & Algorithms

Assignment Help:

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive method for traversal, it need to be an iterative process; meaning, all of steps for the traversal of a node need to be under a loop so that the similar can be applied to all the nodes in the tree.

Algorithm: Non-recursive preorder binary tree traversal

Stack S

push root onto S

repeat until S is empty

{

v = pop S

if v is not NULL

visit v

push v's right child onto S

push v's left child onto S

}

Program 5 illustrates the program segment for the implementation of non- recursive preorder traversal.

 

/* preorder traversal of a binary tree, implemented via a stack */

void preorder(binary_tree_type *tree)

{

stack_type *stack;

stack = create_stack();

push(tree, stack);          /* push the first element of the tree onto the stack */

while (!empty(stack))

{

tree = pop(stack);

visit(tree);

push(tree->right, stack); /* push right child onto the stack */

push(tree->left, stack);    /* push left child onto the stack */

}

}


Related Discussions:- Non-recursive implementation of binary tree traversals

Simulation of queues, Simulation is the process of making an abstract model...

Simulation is the process of making an abstract model of a real world situation in order to be aware of the effect of modifications and alterations and the effect of introducing nu

Doubly linked list having n nodes, The time required to delete a node x fro...

The time required to delete a node x from a doubly linked list having n nodes is O (1)

Explain the term heuristics searching, (a) Discuss the role played by Busin...

(a) Discuss the role played by Business Intelligence Systems in giving companies strategic advantage. (b) Explain the term heuristics searching . (c) With the use of an appr

Explain backtracking, Explain Backtracking The  principal idea is to co...

Explain Backtracking The  principal idea is to construct solutions single component  at a time  and evaluate such  partially constructed candidates as follows. If a partiall

Hashing and collisions during hashing, Q. What do you understand by the te...

Q. What do you understand by the term Hashing?  How do the collisions occur during hashing?  Explain the different techniques or methods for resolving the collision.

Binary search, Write the algorithm for Binary search. Also apply this algo...

Write the algorithm for Binary search. Also apply this algorithm on the following data. 22, 44, 11, 88, 33, 55, 77, 66

Graph terminologies, Graph terminologies : Adjacent vertices: Two vert...

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

Explain time complexity, Time Complexity:- The time complexity of an algori...

Time Complexity:- The time complexity of an algorithm is the amount of time it requires to run to completion. Some of the reasons for studying time complexity are:- We may be in

Complexity of an algorithm, What do you mean by complexity of an algorithm?...

What do you mean by complexity of an algorithm? The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space need of the algorithm i

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd