Non Recursive Algorithm to Traverse a Binary Tree, Data Structure & Algorithms

Q. Write down a non recursive algorithm to traverse a binary tree in order.                   

Ans:

Non - recursive algorithm to traverse a binary tree in inorder is as follows:-

Initially in the beginning   push NULL  onto STACK  and then set  PTR  = ROOT. Then    repeat the steps written below until   NULL is popped from STACK.

i.      Continue down the left -most path rooted at PTR, pushing each node N onto STACK and stopping when a node     N    with no left    child     is   pushed    onto

STACK.

ii.    [Backtracking.] Pop and  process the nodes on

STACK. If the NULL is popped then Exit. If a node N

Having a right child R(N) is processed, set PTR = R(N) (by assigning PTR = RIGHT[PTR] and return to the Step(a)).

 

 

Posted Date: 7/10/2012 5:56:43 AM | Location : United States







Related Discussions:- Non Recursive Algorithm to Traverse a Binary Tree, Assignment Help, Ask Question on Non Recursive Algorithm to Traverse a Binary Tree, Get Answer, Expert's Help, Non Recursive Algorithm to Traverse a Binary Tree Discussions

Write discussion on Non Recursive Algorithm to Traverse a Binary Tree
Your posts are moderated
Related Questions
A Red-Black Tree (RBT) is a type of Binary Search tree with one extra bit of storage per node, i.e. its color that can either be red or black. Now the nodes can have any of the col

What is Space complexity of an algorithm? Explain.

In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm. In this method,

Explain divide and conquer algorithms  Divide  and  conquer  is  probably  the  best  known  general  algorithm  design  method.  It   work according to the following general p

We have discussed already about three tree traversal methods in the earlier section on general tree. The similar three different ways to do the traversal -inorder , preorder, and p

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

The above 3 cases are also considered conversely while the parent of Z is to the right of its own parent. All the different kind of cases can be illustrated through an instance. Le

As we talked in class, a program with two integer variables is universal. Now, we consider a special form of four variableprograms. Let G = (V; E) be a directed graph, where V is a

What are the conditions under which sequential search of a list is preferred over binary search? Sequential Search is a preferred over binary search when the list is unordered

DEPTH FIRST SEARCH (DFS) The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisite