LeetCode Problem: 1028. Recover a Tree From Preorder Traversal

Problem Statement:

Recover binary tree from its given preorder traversal string. The string is given in the format: Dashes followed by value. The number of dashes convey its depth and value refers to the node value.

Example 1:

Input:

string = "1-2--3--4-5--6--7";

Output:

[1,2,5,3,4,6,7]

Example 2:

Input:

string = "1-2--3---4-5--6---7";

Output:

[1,2,5,3,null, 6, null, 4, null, 7]

Example 3:

Input:

string = "1-401--349---90--88";

Output:

[1,401,null,349,88,90].

Approach to the solution:

1. Calculate value and its depth
2. Check if right child is present. If yes then move to right child then go to step 2 again until depth of the node is reached.
3. Else move to left and then go to step 2 again until depth of the node is reached.
4. Once the calculated depth is reached.
5. If left child of the node is null, create a new node and assign left child of the node.
6. Else create a new node and assign it to right child.
7. Continue from step 1 again until end of the string is reached.

Solution in C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
            int iter = 0;
            int depth = 0;
            int num   = 0;
        num   = GetNum(S, iter);
        TreeNode* root = new TreeNode(num);
        while(iter < S.length()){
            depth = GetDepth(S, iter);
            num   = GetNum(S, iter);
            InsertIntoTree(root, depth, num);
        }
        return root;
    }
private:

    void InsertIntoTree(TreeNode* node, int depth, int value){
        while(--depth > 0){
            if(node->right){
                node = node->right;
            } else if(node->left){
                node = node->left;
            }
        }
        TreeNode *temp = new TreeNode(value);
        if(node->left == nullptr){
            node->left = temp;
        } else {
            node->right = temp;
        }
    }
    int GetDepth(string S, int &iter){
            int count = 0;
        while(S[iter] == '-'){
            ++iter;
            ++count;
        }
        return count;
    }    
    int GetNum(string S, int &iter){
            int num = 0;
        while(S[iter] != '-' && iter < S.length()){
            num = num * 10 + (int)(S[iter] - 48);
            ++iter;
        }
        return num; 
    }
};