In-order traversal, Data Structure & Algorithms

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







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
Related Questions
In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

Assume you are in the insurance business. Find two examples of Type 2 slowly changing dimensions in that business. As an analyst on the project, write the specifications for applyi

Binary Space Partition A binary space-partitioning (BSP) tree is an efficient method for determining object visibility by painting surfaces onto the screen from back to front,

a. Explain the sum of subset problem. Apply backtracking to solve the following instance of sum of subset problem: w= (3, 4, 5, 6} and d = 13. Briefly define the method using a sta

Define the terms     i) Key attribute     ii) Value set  Key attribute:  An entity  type  usually  has  an attribute  whose  values  are  distinct  fr

For a queue a physical analogy is a line at booking counter. At booking counter, customers go to the rear (end) of the line & customers are attended to several services from the fr

D elete a specific Node from Double Linked List as follows DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FORW [ BACK [LOC]]:= FORW[LOC]& BACK [FORW[

It does not have any cycles (circuits, or closed paths), which would imply the existence of more than one path among two nodes. It is the most general kind of tree, and might be co

Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of