problem84.cpp

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left, *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class SortedArrayToBST {
  vector<int> nums;

public:
  void readInput() {
    string line;
    getline(cin, line);
    istringstream iss(line);
    int num;
    while (iss >> num) nums.push_back(num);
  }

  TreeNode* buildBST(int left, int right) {
    if (left > right) return NULL;
    int mid = left + (right - left) / 2;
    TreeNode* node = new TreeNode(nums[mid]);
    node->left = buildBST(left, mid - 1);
    node->right = buildBST(mid + 1, right);
    return node;
  }

  vector<string> levelOrder(TreeNode* root) {
    vector<string> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
      TreeNode* curr = q.front(); q.pop();

      if (curr) {
        result.push_back(to_string(curr->val));
        q.push(curr->left);
        q.push(curr->right);
      } else {
        result.push_back("null");
      }
    }
    
    while (!result.empty() && result.back() == "null") result.pop_back();

    return result;
  }

  void display() {
    TreeNode* root = buildBST(0, nums.size() - 1);
    vector<string> level = levelOrder(root);
    for (int i = 0; i < level.size(); ++i) {
      if (i) cout << " ";
      cout << level[i];
    }
    cout << endl;
  }
};

int main() {
  SortedArrayToBST solver;
  solver.readInput();
  solver.display();
  return 0;
}