problem83.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 CompleteTreeCounter {
  string line;
  TreeNode *root;

public:
  void readInput() {
    getline(cin, line);
    if (line.empty()) {
      cout << "!! Invalid Input !!" << endl;
      exit(1);
    }
    root = buildTree();
  }

  TreeNode *buildTree() {
    istringstream iss(line);
    string val;
    vector<string> nodes;

    while (iss >> val) nodes.push_back(val);
    if (nodes[0] == "null") return nullptr;

    TreeNode *root = new TreeNode(stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;

    while (!q.empty() && i < nodes.size()) {
      TreeNode *curr = q.front();
      q.pop();

      if (i < nodes.size() && nodes[i] != "null") {
        curr->left = new TreeNode(stoi(nodes[i]));
        q.push(curr->left);
      }
      i++;

      if (i < nodes.size() && nodes[i] != "null") {
        curr->right = new TreeNode(stoi(nodes[i]));
        q.push(curr->right);
      }
      i++;
    }

    return root;
  }

  int countNodes(TreeNode *node) {
    if (!node) return 0;

    int leftDepth = getDepth(node->left);
    int rightDepth = getDepth(node->right);

    if (leftDepth == rightDepth) {
      return (1 << leftDepth) + countNodes(node->right);
    } else {
      return (1 << rightDepth) + countNodes(node->left);
    }
  }

  int getDepth(TreeNode *node) {
    int d = 0;
    while (node) {
      d++;
      node = node->left;
    }
    return d;
  }

  void display() {
    cout << countNodes(root) << endl;
  }
};

int main() {
  CompleteTreeCounter ctc;
  ctc.readInput();
  ctc.display();
  return 0;
}