1
class Solution {
2
 public:
3
  // Returns the index of '-' if present otherwise returns the string length
4
  int findIndex(int ind, string &traversal) {
5
    int req = traversal.size();
6
    for (int i = ind; i < traversal.size(); i++) {
7
      if (traversal[i] == '-') {
8
        req = i;
9
        break;
10
      }
11
    }
12
    return req;
13
  }
14

15
  TreeNode *recoverFromPreorder(string traversal) {
16
    // Pushing the node along with its depth into the stack
17
    int depth = 0;
18
    stack<pair<TreeNode *, int>> st;
19

20
    // Finding the root node
21
    int ind = findIndex(0, traversal);
22
    string str = traversal.substr(0, ind);
23
    TreeNode *root = new TreeNode(stoi(str));
24

25
    // Pushing the root node along with its depth
26
    st.push({root, 0});
27

28
    // Starting from 'ind' as it has the next '-' character
29
    int i = ind;
30

31
    while (i < traversal.size()) {
32
      // Increment the depth
33
      if (traversal[i] == '-') {
34
        depth++;
35
        i++;
36
        continue;
37
      }
38

39
      // Find the complete number as no.of digits can be > 1
40
      int ind = findIndex(i, traversal);
41
      string str = traversal.substr(i, ind - i);
42
      TreeNode *node = new TreeNode(stoi(str));
43

44
      // Finding its appropriate parent, whose depth is one less than current
45
      // depth
46
      while (!st.empty() && st.top().second != depth - 1) {
47
        st.pop();
48
      }
49

50
      // There is already left child for the parent
51
      if (st.top().first->left) {
52
        st.top().first->right = node;
53
      } else {
54
        st.top().first->left = node;
55
      }
56

57
      // Pushing that node and its depth into stack
58
      st.push({node, depth});
59
      depth = 0;
60
      i = ind;
61
    }
62

63
    return root;
64
  }
65
};