#include <iostream>
#include <functional>
#include <stack>

struct tNode {
  char data;
  struct tNode *left;
  struct tNode *right;
};

// Function to create a new node
tNode *newNode(char data) {
  tNode *node = new tNode;
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  return node;
}

// Function to insert nodes in level order
tNode *insertLevelOrder(char arr[], tNode *root, int i, int n) {
  // Base case for recursion
  if (i < n) {
    tNode *temp = newNode(arr[i]);
    root = temp;

    // insert left child
    root->left = insertLevelOrder(arr, root->left, 2 * i + 1, n);

    // insert right child
    root->right = insertLevelOrder(arr, root->right, 2 * i + 2, n);
  }
  return root;
}

// Function to delete the given tree
void deleteTree(tNode *node) {
  if (node == NULL)
    return;

  /* first delete both subtrees */
  deleteTree(node->left);
  deleteTree(node->right);

  /* then delete the node */
  // std::cout << "Deleting node: " << node->data << std::endl;
  delete node;
}
void in_order(tNode* node, const std::function<void(tNode*)>& visitor) {
    if (node == nullptr) {
    	return;
    };
    in_order(node->left, visitor);
    visitor(node);
    in_order(node->right, visitor);
}
void pre_order_stack(tNode* root, const std::function<void(tNode*)>& visitor) {
    std::stack<tNode*> stack;
    stack.push(root);
    while (!stack.empty()) {
        tNode *curr = stack.top();
        stack.pop();
        visitor(curr);
        // With this approach we visit "null" nodes, which can be useful.
        // Alternatively we could move the condition to the push:
        //if (curr->right != nullptr) stack.push(curr->right);
        if (curr == nullptr) continue;

        if (curr->right!=NULL) {
            stack.push(curr->right);
        }
        if (curr->left!=NULL) {
            stack.push(curr->left);
        }

    }
}
void post_order_nonrecursive(tNode *root, const std::function<void(tNode*)>& visitor) {
    std::stack<tNode*> s;
    tNode *current = root;
    while (true) {
        // Explore left, but remember node & right child
        if (current != nullptr) {
            if (current->right != nullptr)
                s.push(current->right);
            s.push(current);
            current = current->left;
            continue;
        }
        // current == nullptr
        if (s.empty()) return;
        current = s.top();
        s.pop();
        // If we have the right child remembered, 
        // it would be on the top of the stack.
        if (current->right && !s.empty() && current->right == s.top()) {
            // if it is, we must visit it (and it's children) first
            s.pop();
            s.push(current);
            current = current->right;
        } else {
            visitor(current);
            current = nullptr;
        }
    }
}
// Driver program to test above function
int main() {
  char arr[]={'+','2','+',NULL,NULL,'2','*',NULL,NULL,NULL,NULL,NULL,NULL,'2','+',NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,'2','2'};
  tNode *root = insertLevelOrder(arr, root, 0, 31);
  in_order(root, [](tNode* node){std::cout << node->data << " ";});
  std::cout<<"\n";
  pre_order_stack(root, [](tNode* node){std::cout << node->data << " ";});
  std::cout<<"\n";
  post_order_nonrecursive(root, [](tNode* node){std::cout << node->data << " ";});
  deleteTree(root);
  root = NULL;

  return 0;
}