#include <iostream>
using namespace std;
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 */
  cout<<(node->data)<<" ";
  deleteTree(node->left);
  deleteTree(node->right);

  /* then delete the node */
  // std::cout << "Deleting node: " << node->data << std::endl;
  delete node;
}
void preorder(tNode *node) {
  if (node == NULL)
    return;
  /* first delete both subtrees */
  cout<<(node->data)<<" ";
  preorder(node->left);
  preorder(node->right);
}
void inorder(tNode *node) {
  if (node == NULL)
    return;
  /* first delete both subtrees */
  inorder(node->left);
  cout<<(node->data)<<" ";
  inorder(node->right);
}
// Driver program to test above function
int main() {
  int size = 3;
  char arr[size]={'+','a','b'}; // Create an array of elements
  
  tNode *root = insertLevelOrder(arr, root, 0, size);
  inorder(root);
  deleteTree(root);
  root = NULL;

  return 0;
}