Post order traversal, Data Structure & Algorithms

Post order traversal:

The children of node are visited before the node itself; the root is visited last. Each node is visited after its descendents are visited.

Algorithm for postorder traversal is following:

1. Traverse left sub-tree in post order

2. Traverse right sub-tree in post order

3. visit root node.

Determining the space occupied through files & directories in a file system need a postorder traversal as the space occupied through directory needs calculation of space needed by all files in the directory (children in tree structure)

2078_Post order traversal.png

          Figure:  Calculation of space occupied by a file system: A post order traversal

Since each of the nodes is traversed only once, the time complexity of post order traversal is T(n) = O(n), where n refer to number of nodes in the tree.

Posted Date: 4/10/2013 2:09:48 AM | Location : United States







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

Write discussion on Post order traversal
Your posts are moderated
Related Questions
1)      Why space complexity is comparatively more critical than time complexity? 2)      Determine the space complexity of Euclid Algorithm?

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

The smallest element of an array's index is called its Lower bound.

Explain the representations of graph. The different ways of representing a graph is: Adjacency list representation : This representation of graph having of an array Adj of

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

floyd warshall algorithm

P os t - o r d e r T r av er sal :  This can be done by both iteratively and recursively. The iterative solution would require a modification or alteration of the in-

In this unit, we have learned how the stacks are implemented using arrays and using liked list. Also, the advantages and disadvantages of using these two schemes were discussed. Fo

Colouring The use of colours in CAD/CAM has two main objectives : facilitate creating geometry and display images. Colours can be used in geometric construction. In this case,

Thus far, we have seen the demonstration of a single queue, but several practical applications in computer science needs several queues. Multi queue is data structure in which mult