Recover a Tree From Preorder Traversal

Leetcode Problem:

• Recover a Tree From Preorder Traversal

Summary

• Recover a binary tree from a preorder depth-first search traversal.

Approach

• The approach used in the solution is to recursively parse the traversal string and construct the binary tree
• At each node, the depth of the node is determined by the number of dashes before its value
• The solution uses a helper function `makeTree` to recursively construct the tree.

Complexity

• O(n), where n is the number of nodes in the tree, because each node is visited once during the traversal and once during the construction of the tree.

Explanation

• The `makeTree` function takes a pointer to the current node, the current depth, a reference to the traversal string, and a reference to the number of processed characters
• It first checks if all characters have been processed, and if not, it extracts the value of the current node by counting the number of dashes before the next character
• It then recursively constructs the left and right subtrees with the updated depth and processed index
• The `recoverFromPreorder` function initializes the tree construction by calling `makeTree` with the root node and the initial depth and processed index.

Solution Code:

/**
 * 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* makeTree(TreeNode* root, int depth, string& traversal, int &processed){
        if(processed == traversal.size()){
            return nullptr;
        }
        
        int i = processed;
        int curDepth = 0;
        while(i < traversal.size() && traversal[i] == '-'){
            i++;
            curDepth++;
        }
        if(curDepth < depth){
            return nullptr;
        }
        int val = 0;
        while(i < traversal.size() && traversal[i] >= '0' && traversal[i] <= '9'){
            val *= 10;
            val += traversal[i] - '0';
            i++;
        }
        processed = i;
     
        root = new TreeNode();
        root->val = val;
        root->left = makeTree(root->left, depth+1, traversal, processed);
        root->right = makeTree(root->right, depth+1, traversal, processed);
        return root;
    }
    TreeNode* recoverFromPreorder(string traversal) {
        int processed = 0;
        TreeNode* root = makeTree(root, 0, traversal, processed);
        return root;
    }
};