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

Reverse order of elements on a slack, Q. Reverse the order of the elements ... Q. Reverse the order of the elements on a stack S    (i) by using two additional stacks (ii) by using one additional queue. Ans :      L e t S be the stac

For loop, for (i = 0; i sequence of statements } Here, the loop e... for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

State cmy model, CMY Model  The cyan, magenta, yellow (CMY) colour mode... CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard

Conversion of general trees into the binary trees, By taking an appropriate... By taking an appropriate example explain how a general tree can be represented as a Binary Tree.                                                                    C onversio

Doubly linklist, explanation of doubly linklist explanation of doubly linklist

Algorithms, 2. Write a note on i) devising ii) validating and... 2. Write a note on i) devising ii) validating and iii) testing of algorithms.

String manipulation, what is string manipulation? what is string manipulation?

Procedures, what is far and near procedures in system programming? what is far and near procedures in system programming?

Describe data structure?, Typical programming languages such as Pascal, C o... Typical programming languages such as Pascal, C or Java give primitive data kinds such as integers, boolean, reals values and strings. They give these to be organised into arrays,

Define a procedure called make-avl-tree, This question deals with AVL trees... This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o