problem81.cpp

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

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

class DeepestRoots {
  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 NULL;

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

    int i = 1;
    while (!q.empty() && i < nodes.size()) {
      TreeNode* curr = q.front(); q.pop();
      if (nodes[i] != "null") {
        curr->left = new TreeNode(nodes[i]);
        q.push(curr->left);
      }
      i++;
      if (i < nodes.size() && nodes[i] != "null") {
        curr->right = new TreeNode(nodes[i]);
        q.push(curr->right);
      }
      i++;
    }
    return root;
  }

  int maxDepth(TreeNode* node) {
    if (!node) return 0;
    int left = maxDepth(node->left);
    int right = maxDepth(node->right);
    return 1 + max(left, right);
  }

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

int main() {
  DeepestRoots dr;
  dr.readInput();
  dr.display();
  return 0;
}