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
The complexity of searching an element from a set of n elements using Binary search algorithm is   O(log n)

Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

what''s queue ?

Preorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; };   preorder(struct N

Define about the Structure - Container - Some containers hold elements in some sort of structure, and some don't. Containers with no structure include bags and sets. Containe

Comparison Techniques There are several techniques for determining the relevancy and relative position of two polygons. Not all tests may be used with all hidden-surface algori

Q. Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example. A n s . Yes a

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

In any singly linked list, each of the elements contains a pointer to the next element. We have illustrated this before. In single linked list, traversing is probable only in one d