#include <iostream>

template<typename T>
struct TreeNode {
  TreeNode(T value) : parent(nullptr), left(nullptr), right(nullptr) {
    this->value = value;
  }
  ~TreeNode() {
    delete left;
    delete right;
  }
  TreeNode<T>* parent;
  TreeNode<T>* left;
  TreeNode<T>* right;
  T value;
};

const int INVALID = -1;

inline int left_child_idx(int curr, int len) {
  int child = curr * 2 + 1;
  return child < len ? child : INVALID;
}

inline int right_child_idx(int curr, int len) {
  int child = curr * 2 + 2;
  return child < len ? child : INVALID;
}

inline int parent_idx(int curr, int len) {
  return curr == 0 ? INVALID : (curr - 1) / 2;
}

template<typename T>
TreeNode<T>* construct_tree(T* arr, int len) {
  if (len == 0) {
    return nullptr;
  }

  TreeNode<T>* root = new TreeNode<T>(arr[0]);
  TreeNode<T>* curr = root;
  int curr_idx = 0;
  while (curr) {
    if (curr->left == nullptr) {
      // No left child.
      assert(curr->right == nullptr);
      int child_idx = left_child_idx(curr_idx, len);
      if (child_idx != INVALID) {
        TreeNode<T>* child_node = new TreeNode<T>(arr[child_idx]);
        curr->left = child_node;
        child_node->parent = curr;
        curr = child_node;
        curr_idx = child_idx;
        continue;
      }
    } else if (curr->right == nullptr) {
      // Has left child, but no right child.
      int child_idx = right_child_idx(curr_idx, len);
      if (child_idx != INVALID) {
        TreeNode<T>* child_node = new TreeNode<T>(arr[child_idx]);
        curr->right = child_node;
        child_node->parent = curr;
        curr = child_node;
        curr_idx = child_idx;
        continue;
      }
    }
    curr_idx = parent_idx(curr_idx, len);
    curr = curr->parent;
  }
  assert(curr_idx == INVALID);
  return root;
}

void debug_print(TreeNode<int>* node) {
  if (node == nullptr) return;
  printf("(");
  debug_print(node->left);
  printf("%d", node->value);
  debug_print(node->right);
  printf(")");
}

void test(int count) {
  int arr[count];
  for (int i=0; i<count; ++i) {
    arr[i] = i;
  }
  TreeNode<int>* root = construct_tree<int>(arr, count);
  debug_print(root); printf("\n");
  delete root;
}

int main() {
  int input[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (int i = 0; i < 10; ++i) {
    test(i);
  }
}