online advertising

## Sunday, November 27, 2016

### HackerRank - Tree: Postorder Traversal

Problem:

Please find the problem here.

Solution:

Post order traversal is simple, we will skip it.

Note that if we do

postOrder(root->right);
postOrder(root->left);
cout << root->data << " ";

instead of the usual post order, we will get exactly the reverse of pre-order, why?

We will prove that by induction.

the code produce the reverse for tree of height 0 (i.e. null), trivial.

If we assume the code produce the pre-order reverse for tree of height k.

For height k + 1, we have

[reverse of pre-order of right of root] [reverse of pre-order left of root] [root]

The pre-order of root is

[root] [pre-order of left of root] [pre-order of right of root]

So we get exactly the same reverse, by structural induction we proved that the variant post order code will produce exactly the reverse of pre-order.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/tree-postorder-traversal

#include "HACKER_RANK_TREE_POSTORDER_TRAVERSAL.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _HACKER_RANK_TREE_POSTORDER_TRAVERSAL
{
struct node
{
int data;
node* left;
node* right;
};

void postOrder(node *root)
{
if (root == nullptr)
{
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
};

using namespace _HACKER_RANK_TREE_POSTORDER_TRAVERSAL;

int HACKER_RANK_TREE_POSTORDER_TRAVERSAL()
{
node a;
node b;
node c;
node d;
node e;
node f;
a.data = 3;
b.data = 5;
c.data = 2;
d.data = 1;
e.data = 4;
f.data = 6;
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
c.right = nullptr;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
f.left = nullptr;
f.right = nullptr;
postOrder(&a);
return 0;
}