Postorder Tree Traversal: Calculating the Result

[barbara]

The following algorithm describes a postorder tree traversal

Postorder(tree)

If left subtree exists then Postorder(left subtree)

If right subtree exists then Postorder(right subtree)

Print root

end



How can I apply that to the following tree





+

/ \

/ \

* -

/ \ / \

2 3 * +

/ \ / \

4 2 1 5



What is the result of the computation? What kind of algorithm is being used here?

 

[evinda]

Firstly, the pointer shows to +. Then we notice that a left subtree exists , so we call the function Postorder(left subtree) and then the pointer shows to * . Can you continue?

P.S. : At the following part:

+

/ \

/ \

* -

this: / \ should appear only once. Is it a typo?

 

[barbara]

Firstly, the pointer shows to +. Then we notice that a left subtree exists , so we call the function Postorder(left subtree) and then the pointer shows to * . Can you continue?

P.S. : At the following part:

+

/ \

/ \

* -

this: / \ should appear only once. Is it a typo?

Yes its a typo
Thank you for your help and this is what the answer should look like. Please let me know if its correctThe is a representation of a recursion algorithm traverses the left subtree, the right subtree, and finally the root. That carries on the subtrees of the subtrees until a leaf is found. Thus, starting with +

/ \

/ \

* -

/ \ / \

2 3 * +

/ \ / \

4 2 1 5You start with the left subtree of the root, which is *

/ \

2 3The root of this tree is * , and it has a left subtree consisting of the leaf 2, and the right subtree consisting of the leaf 3. Going through the traversal, then this subtree is traversed as 2 3 *Now you expand the right subtree of the root of the tree. That is
-

/ \

* +

/ \ / \

4 2 1 5The left subtree is *

/ \

4 2 The expansion of this tree is 4 2 *The right subtree is is

+

/ \

1 5The expansion of this tree is 1 5 +The root of the right subtree is -so the expansion of the right subtree is (left) (right) (root) 4 3 * 1 5 + -Finallyyou put together the traversal of the entire tree is (left) (right) root2 3 * 4 3 * 1 5 + - +
The value is equal to 8

 

[Evgeny.Makarov]

Barbara, in the future please use a text editor with a fixed-width font to type the tree and then copy and paste it between the [textdraw]...[/textdraw] tags, like this.

[textdraw]
+
/ \
/ \
/ \
* -
/ \ / \
2 3 * +
/ \ / \
4 2 1 5
[/textdraw]

this is what the answer should look like. Please let me know if its correct

How do you know that the answer should look like this if you are not sure whether it is correct?

2 3 * 4 3 * 1 5 + - +

According to the tree, it's 4 2 and not 4 3. Otherwise, it's correct.