Write steps for algorithm for In-order Traversal

This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion or area of a tree twice. The common process of in-order traversal follows the following steps:

1.   push a NULL onto the given stack.

2.   starting with the root, proceed down the left side of the   tree. As long as  there is one more left node  following     the current  node,

push the pointer to the current node onto the stack and move to the left node which follows it.

3.   when there are no further left nodes following the current node, process the current node.

4.   check to see if the last left node has a right node(it   certainly doesn't  have  a  left node).

5.   if  there is a  right node then there will be subtree to the right. This should be further processed in following steps 2   to 4.

6.   if there is no right node in it then pop the last node from the stack (back up one node). Process this node and as this node has a left subtree that     has  already   been     processed, move    to   the right of the node and start looking for a left and right subtree again.

 

 

 

Posted Date: 7/9/2012 10:10:15 PM | Location : United States

Ask an Expert

Related Discussions:- In-order traversal, Assignment Help, Ask Question on In-order traversal, Get Answer, Expert's Help, In-order traversal Discussions

Write discussion on In-order traversal
Your posts are moderated

Write your message here..

Related Questions

Write the algorithm of the quick sort, Ans. An algorithm for the quick... Ans. An algorithm for the quick sort is as follows: void quicksort ( int a[ ], int lower, int upper ) { int i ; if ( upper > lower ) { i = split ( a, lower, up

A full binary tree with n leaves, A full binary tree with n leaves have:- ... A full binary tree with n leaves have:- 2n -1 nodes.

In-order traversal, Write steps for algorithm for In-order Traversal Th... Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

Asymptotic analysis, Asymptotic Analysis Asymptotic analysis is dependi... Asymptotic Analysis Asymptotic analysis is depending on the idea that as the problem size grows, the complexity can be defined as a simple proportionality to some known functio

Explain complexity of an algorithm, Complexity of an Algorithm An algo... Complexity of an Algorithm An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorith

Single pointer pointing to the tail of the queue, Can a Queue be shown by c... Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

Define container in terms of object-oriented terms, Define container in te... Define container in terms of  object-oriented terms A Container is a broad category whose instances are all more specific things; there is never anything which is just a Contai

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8... Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

Define queue fifo ?, A queue is a particular type of collection or abstract... A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

Abstract data types, Abstract Data Types :- A useful tool for specifying th... Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem