Post order traversal, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Post order traversal

Usage of linked lists for polynomial manipulation, Q. Establish the usage o...

Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

Sort the Sequence Using Merge Sort, Q. Sort the sequence written below of k...

Q. Sort the sequence written below of keys using merge sort. 66, 77, 11, 88, 99, 22, 33, 44, 55                                                                      Ans:

Determine relevancy and relative position of two polygons, Comparison Techn...

Comparison Techniques There are several techniques for determining the relevancy and relative position of two polygons. Not all tests may be used with all hidden-surface algori

Linear array - numerical, Q. A linear array A is given with lower bound as ...

Q. A linear array A is given with lower bound as 1. If address of A[25] is 375 and A[30] is 390, then find address of A[16].

Binary search tree bst, Describe Binary Search Tree (BST)? Make a BST for t...

Describe Binary Search Tree (BST)? Make a BST for the given sequence of numbers. 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48 Traverse the obtained tree in Preorder, Inord

Pipelining., How branching takes place in Instruction pipeline. Explain wit...

How branching takes place in Instruction pipeline. Explain with suitable examples

Bubble sort, Q. The reason bubble sort algorithm is inefficient is that it ...

Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comp

Dgsd, Ask question #sdgsdgsdginimum 100 words accepted#

Ask question #sdgsdgsdginimum 100 words accepted#

Size of stack, The size of stack was declared as ten. Thus, stack cannot ho...

The size of stack was declared as ten. Thus, stack cannot hold more than ten elements. The major operations which can be performed onto a stack are push and pop. However, in a prog

What is a linear array, What is a linear array? An array is a way to re...

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd