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)

          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

Ask an Expert

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

Write your message here..

Related Questions

Determine the space complexity of euclid algorithm, 1)      Why space compl... 1)      Why space complexity is comparatively more critical than time complexity? 2)      Determine the space complexity of Euclid Algorithm?

The theta-notation, This notation bounds a function to in constant factors.... 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, The smallest element of an array... The smallest element of an array's index is called its Lower bound.

Explain the representations of graph, Explain the representations of graph.... 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

Implement an algorithm to simulate car re-organizing, Design  and implement... 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

Graphs, floyd warshall algorithm floyd warshall algorithm

Write algorithm for post-order traversal, P os t - o r d e r T ... 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-

Implementation of stack, In this unit, we have learned how the stacks are i... 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

Explain the concept of colouring, Colouring The use of colours in CAD/C... 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,

Implementation of multiple queues, Thus far, we have seen the demonstration... 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