Recover A Tree From Preorder Traversal - Leetcode Solution

Problem Statement:

We are given a string s that represents a preorder traversal of a binary tree. The string s is encoded the following way:

• Nodes are represented as s followed by one of the symbols '-' or '+'. '-' represents a left child, and '+' represents a right child.
• If a node has value val, the string will contain val truncated to its decimal representation (without leading zeroes).
• Each node in the tree has either 0 or 2 children.

Return the root of the binary tree represented by s.

Solution:

There are multiple ways to solve this problem, but the most common solution is to use a stack to iterate through the input string and build the binary tree. We will start by creating the root node, which will be the first element of the string. Then, we will iterate through the rest of the string, and for each node:

• If it is a left child, we will create a new node and set it as the left child of the current node.
• If it is a right child, we will create a new node and set it as the right child of the parent of the current node. We will keep popping nodes from the stack until we find a node with a smaller depth than the current node.

Algorithm:

• Create an empty stack.
• Parse the first node in the string to create the root of the tree.
• Push the root onto the stack.
• Iterate through the rest of the string, character by character.
• If the current character is a digit, keep parsing it until the end of the number to get the value of the current node.
• If the current character is a '-', it means the current node is a left child. Create a new node with the parsed value, set it as the left child of the current node, and push it onto the stack.
• If the current character is a '+', it means the current node is a right child. Create a new node with the parsed value, set it as the right child of the parent of the current node, and keep popping nodes from the stack until we find a node with a smaller depth than the current node.
• Return the root of the tree.

Pseudo code:

define function recoverFromPreorder(s: str) -> TreeNode: stack = [] i = 0

while i < len(s):
    depth = 0
    while i < len(s) and s[i] == '-':
        depth += 1
        i += 1
    
    value = 0
    while i < len(s) and s[i].isdigit():
        value = value * 10 + int(s[i])
        i += 1
    
    node = TreeNode(value)
    
    while len(stack) > depth:
        stack.pop()
        
    if stack and stack[-1].left is None:
        stack[-1].left = node
    elif stack:
        stack[-1].right = node
        
    stack.append(node)
    
return stack[0]

Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the input string s.

Space Complexity: The space complexity of this algorithm is O(h), where h is the height of the binary tree. This is because we are using a stack to keep track of the nodes in the tree, and the maximum size of the stack is equal to the height of the tree.

1