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
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 (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

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

By taking an appropriate example explain how a general tree can be represented as a Binary Tree.                                                                    C onversio

explanation of doubly linklist

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

what is far and near procedures in system programming?

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,

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