Recover a Tree From Preorder Traversal

class Solution {
public:
    TreeNode* buildTreeFromPreorder(string input) {
        vector<TreeNode*> nodeStack;
        int pos = 0, len = input.length();
    
        while (pos < len) {
            // Calculating depth by counting dashes
            int level = 0;
            while (pos < len && input[pos] == '-') {
                level++;
                pos++;
            }
    
            // Getting numeric value of node
            int nodeVal = 0;
            while (pos < len && isdigit(input[pos])) {
                nodeVal = nodeVal * 10 + (input[pos] - '0');
                pos++;
            }
    
            // Creating new TreeNode
            TreeNode* newNode = new TreeNode(nodeVal);
    
            // Adjusting the stack to the current tree depth
            if (level < nodeStack.size()) {
                nodeStack[level] = newNode;
            } else {
                nodeStack.push_back(newNode);
            }
    
            // Linking current node to its parent, if applicable
            if (level > 0) {
                TreeNode* parentNode = nodeStack[level - 1];
                if (!parentNode->left) {
                    parentNode->left = newNode;
                } else {
                    parentNode->right = newNode;
                }
            }
        }
    
        // The very first node is the root
        return nodeStack[0];
    }
};

This C++ solution focuses on constructing a binary tree from a given preorder traversal string where levels are denoted by dashes -. Here is a breakdown of how the solution functions:

• Initialize a vector nodeStack to hold the nodes at various levels of the tree.
• Loop through the string using index variable pos. For each character in the string:
  • Count the number of consecutive dashes to determine the current level of the tree node.
  • Parse the subsequent characters to extract the numeric value of the node until a non-digit is encountered.
  • Create a new tree node newNode with the extracted value.
  • Adjust nodeStack so that it aligns with the current tree depth. If the current level is less than the size of nodeStack, replace the node at that level with newNode. If not, add newNode to nodeStack.
  • If not at the root level (i.e., level > 0), link the new node to its parent node, which resides in the previous level of the stack. If the left child of the parent is null, assign the new node to it. Otherwise, assign it to the right child.
• Return the first node in nodeStack as it serves as the root of the constructed binary tree.

This solution meticulously rebuilds the tree by placing each node at its correct depth using the stack adjustment technique, ensuring the tree structure reflects the preorder traversal as described by the input string.

class Solution {
    
    public TreeNode buildTreeFromPreorder(String sequence) {
        // Keeps track of node tree structure at various depths
        List<TreeNode> treeDepth = new ArrayList<>();
        int pos = 0, strLen = sequence.length();
    
        while (pos < strLen) {
            // Calculate the depth using dashes
            int depth = 0;
            while (pos < strLen && sequence.charAt(pos) == '-') {
                depth++;
                pos++;
            }
    
            // Read the numerical value of node
            int value = 0;
            while (pos < strLen && Character.isDigit(sequence.charAt(pos))) {
                value = value * 10 + (sequence.charAt(pos) - '0');
                pos++;
            }
    
            // Create new tree node
            TreeNode current = new TreeNode(value);
    
            // Ensure tree structure capacity for new depth
            if (depth < treeDepth.size()) {
                treeDepth.set(depth, current);
            } else {
                treeDepth.add(current);
            }
    
            // Connect new node with the parent node
            if (depth > 0) {
                TreeNode parent = treeDepth.get(depth - 1);
                if (parent.left == null) {
                    parent.left = current;
                } else {
                    parent.right = current;
                }
            }
        }
    
        // Root node is at depth 0, return it
        return treeDepth.get(0);
    }
}

The Java solution provided tackles the problem of reconstructing a binary tree from a given preorder traversal string format, which includes values and dashes indicating depth levels of nodes. The primary steps followed in the algorithm are outlined as follows:

1. Maintain a list (treeDepth) to keep track of nodes at each depth.

2. Traverse each character of the input sequence. Use a loop to process each character until reaching the end of the sequence.

3. Calculate the depth of the current node by counting consecutive dashes. This is achieved by incrementing the depth for each '-' found, moving the position indicator forward.

4. After determining the depth, read the next set of digits in the sequence, which represent the node's value. Convert these characters to an integer.

5. Create a new node (current) with the derived value.

6. Ensure that the treeDepth list can accommodate the current depth. Adjust the list by either resetting the current depth value with the new node or appending the new node if it doesn't yet exist for this depth.

7. Establish parent-child relationships. If the current depth is greater than zero, retrieve the parent node from treeDepth at the parent depth (current depth - 1) and set the current node as the left or right child depending on whether the left child exists.

8. Continue the loop until all characters in the sequence are processed.

9. Finally, return the root of the tree which corresponds to the node at depth 0 in treeDepth.

This method effectively constructs the tree in-place, with a space complexity proportional to the depth of the tree and a time complexity that is linear in relation to the length of the input sequence. This approach harnesses the simplicity and efficiency of list indexing to dynamically manage the tree nodes relative to their depths and nodes' parent-child relationships.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
    
class Solution:
    def restoreTreeFromPreorder(self, input_string: str) -> Optional[TreeNode]:
        level_tracker = []  # Maintain nodes by their level
        pos, length = 0, len(input_string)
    
        while pos < length:
            # Determine the depth by counting dashes
            lvl = 0
            while pos < length and input_string[pos] == "-":
                lvl += 1
                pos += 1
    
            # Read the node value
            node_val = 0
            while pos < length and input_string[pos].isdigit():
                node_val = node_val * 10 + int(input_string[pos])
                pos += 1
    
            # Create a new TreeNode
            current_node = TreeNode(node_val)
    
            # If current level already has a node, replace it, else add new
            if lvl < len(level_tracker):
                level_tracker[lvl] = current_node
            else:
                level_tracker.append(current_node)
    
            # Attach the new node to its corresponding parent node
            if lvl > 0:
                parent_node = level_tracker[lvl - 1]
                if not parent_node.left:
                    parent_node.left = current_node
                else:
                    parent_node.right = current_node
    
        # Root of the tree is the first element in level_tracker
        return level_tracker[0]

Recover a Tree From Preorder Traversal

This Python solution involves reconstructing a binary tree from a given preorder traversal string. Employ the provided Python code to efficiently transform the isolation of string dash levels and numerical values into a tree structure using TreeNode.

1. Initialize a list, level_tracker, to keep track of nodes at different tree levels.

2. Use two variables, pos and length, to manage your current position within the input string and its total length, facilitating loop control.

3. Loop through input_string:

   • Assess the depth of the current node by counting consecutive hyphens, adjusting pos accordingly.
   • Parse the node value immediately following the last dash till a non-digit is encountered, updating pos.
   • Create a new tree node, current_node, from the node_val.

4. Insert or replace the current node in level_tracker based on its depth:

   • If the depth (lvl) is less than the current length of level_tracker, replace the node at that level; otherwise, append the new node.

5. Integrate current_node with its corresponding parent:

   • Identify the parent from level_tracker using index lvl-1.
   • Assign current_node to the left child if it's absent; otherwise, assign it to the right child.

After processing, the root node of your tree, housed at the start of level_tracker, can be returned as the overall tree structure. This approach efficiently couples parsing of preorder data with tree reconstruction.

By structuring this algorithm with distinct and systematic steps for depth identification, node creation, and node integration, you ensure that your binary tree accurately represents the serialized structure provided by input_string.