Logo 
Search:

C++ Programming FAQ

Submit Interview FAQ
Home » Interview FAQ » C++ ProgrammingRSS Feeds

Iterative algorithm for traversing a binary tree in postorder in dfs (data file structure).

  Shared By: Klarissa Schmidt    Date: Jun 21    Category: C++ Programming    Views: 2667

Answer:

PROCEDURE POSTORDER(T)
[Given a binary tree whose root node address is given by the pointer variable T, this algorithm traverses the tree in postorder in an iterative manner].

1. [Initialize]

If T = NULL
then write (“Empty Tree”)
return
else
P <-- T
TOP <-- 0
Call push(S,TOP,T).

2. [Process each stack branch address]

Repeat step 5 while TOP > 0.

3. [Descend left]

while P != NULL
call push(S,TOP,P)
P <-- LPTR(P)

4. [Process a node whose left and right subtree have been processed]

Repeat while S[TOP] > 0
P <-- pop(S,TOP)
write DATA(P)
if TOP = 0
return.

5. [Branch right and then mask node from which we branched]

P <-- RPTR(S[TOP]
S[TOP] <-- - S[TOP].

6. [FINISH]
return.

Share: 
 



Your Comment
  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].


Tagged: