« Post-order traversal of tree

Copy
1#include <iostream>
2#include <queue>
3#include <vector>
4using namespace std;
5
6template <typename T>
7class TreeNode {
8   public:
9    T data;
10    vector<TreeNode<T>*> children;
11
12    TreeNode(T data) { this->data = data; }
13
14    ~TreeNode() {
15        for (int i = 0; i < children.size(); i++) {
16            delete children[i];
17        }
18    }
19};
20
21void printPostOrder(TreeNode<int>* root) {
22    // Write your code here
23    if(root == NULL){
24        return;
25    }
26    for(int i=0; i<root->children.size(); i++){
27        printPostOrder(root->children[i]);
28    }
29    cout<<root->data<<" ";
30}
31
32TreeNode<int>* takeInputLevelWise() {
33    int rootData;
34    cin >> rootData;
35    TreeNode<int>* root = new TreeNode<int>(rootData);
36
37    queue<TreeNode<int>*> pendingNodes;
38
39    pendingNodes.push(root);
40    while (pendingNodes.size() != 0) {
41        TreeNode<int>* front = pendingNodes.front();
42        pendingNodes.pop();
43        int numChild;
44        cin >> numChild;
45        for (int i = 0; i < numChild; i++) {
46            int childData;
47            cin >> childData;
48            TreeNode<int>* child = new TreeNode<int>(childData);
49            front->children.push_back(child);
50            pendingNodes.push(child);
51        }
52    }
53
54    return root;
55}
56
57int main() {
58    TreeNode<int>* root = takeInputLevelWise();
59    printPostOrder(root);
60}