Jobs

Interviews

Discussions

Recover a Tree From Preorder Traversal

Hard

Asked by:

More companies

70 views

Topics:

TreesRecursionStacks

We run a preorder depth-first search (DFS) on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.

If a node has only one child, that child is guaranteed to be the left child.

Given the output traversal of this traversal, recover the tree and return its root.

Example 1:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Constraints:

The number of nodes in the original tree is in the range [1, 1000].
1 <= Node.val <= 10⁹

Try coding it in LeetCode

Recover a Tree From Preorder Traversal

Hard

Asked by:

70 views

Topics:

TreesRecursionStacks

We run a preorder depth-first search (DFS) on the root of a binary tree.

If a node has only one child, that child is guaranteed to be the left child.

Given the output traversal of this traversal, recover the tree and return its root.

Example 1:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Constraints:

The number of nodes in the original tree is in the range [1, 1000].
1 <= Node.val <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the `traversal` string, and what is the maximum depth of the binary tree?
Can the single-digit node values be zero?
Is the input `traversal` string always guaranteed to represent a valid preorder traversal of a binary tree, or should I handle cases where it's malformed?
If the input string is empty, should I return null, or is that considered an invalid input?
Are the number of dashes strictly indicative of the depth relative to the parent, or can there be gaps (e.g., '--1---2' where '2' should still be a child of '1')?

Brute Force Solution

Approach

The brute force way to rebuild the tree is to try every single tree structure possible using the given order. We generate all possible combinations of left and right subtrees. For each combination, we check if it matches the provided traversal order, and if it does, we have a possible solution.

Here's how the algorithm would work step-by-step:

Start by considering the first number in the traversal as the root of the tree.
Then, try all the possible ways to divide the remaining numbers into a left subtree and a right subtree.
For each of these divisions, treat the left subtree numbers as a separate, smaller problem and repeat the process: pick the first number as the root, and try all possible left/right splits within those numbers.
Do the same for the right subtree numbers.
Continue dividing and creating subtrees until you've used up all the numbers in the traversal.
Each time you build a complete tree structure, compare it to the original traversal order to see if it matches.
If a tree structure matches the given traversal, it is a valid solution. If multiple structures match, you can pick any one (or choose based on some criteria, if specified).
If you've exhausted all possible tree structures and none match, then there is no solution to the problem.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def recover_tree_brute_force(preorder):
    if not preorder:
        return None

    root_value = preorder[0]
    root = Node(root_value)

    if len(preorder) == 1:
        return root

    for i in range(len(preorder)):
        left_subtree_preorder = preorder[1:i+1]
        right_subtree_preorder = preorder[i+1:]

        # Recursively build left and right subtrees
        left_subtree = recover_tree_brute_force(left_subtree_preorder)
        
        right_subtree = recover_tree_brute_force(right_subtree_preorder)

        root.left = left_subtree
        root.right = right_subtree

        # Check if the generated tree's preorder matches the input
        if is_valid_tree(root, preorder):
            return root

        root.left = None
        root.right = None

    return None

def is_valid_tree(root, preorder):
    tree_preorder = generate_preorder(root)
    return tree_preorder == preorder

def generate_preorder(root):
    if not root:
        return []

    preorder_list = [root.value]
    preorder_list.extend(generate_preorder(root.left))
    preorder_list.extend(generate_preorder(root.right))
    return preorder_list

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach involves exploring all possible binary tree structures that can be formed from the given preorder traversal of size n. In the worst case, each node can potentially have either a left child, a right child, or no child, leading to an exponential number of possible tree configurations. The algorithm essentially tries all possible combinations of left and right subtrees at each step, generating a full binary tree, which is equivalent to finding all possible binary trees, a count that is related to Catalan numbers. Thus, the time complexity is exponential, specifically O(2^n).

Space Complexity

O(N^2) – The brute force approach described generates all possible tree structures by dividing the input list into left and right subtrees recursively. Each recursive call creates temporary lists to represent these subtrees, and in the worst-case scenario, there could be N levels of recursion. Within each level of the recursion, memory is used to store intermediate results, and there could be up to N splits/combinations to analyze, creating more temporary list structures that contribute to the auxiliary space. Thus, the auxiliary space would approximate to N levels of recursion with N amount of temporary data being stored, resulting in O(N^2) space complexity.

Optimal Solution

Approach

The optimal solution reconstructs the tree using the properties of the preorder traversal. The key is to use the depth indicated by the number of dashes to guide where each node belongs in the tree. We leverage a stack to keep track of potential parent nodes as we walk through the preorder traversal string.

Here's how the algorithm would work step-by-step:

Begin processing the preorder string from left to right, one node at a time.
For the current node, determine its depth by counting the number of dashes preceding its value.
While the stack isn't empty and the depth of the current node is less than or equal to the depth of the last node in the stack, remove the last node from the stack. This ensures we are always considering the correct parent for the current node.
Create a new node with the current value.
If the stack is not empty, the last node in the stack is the parent of the current node. Check if the parent node already has a left child. If not, the current node becomes the left child; otherwise, it becomes the right child.
Push the new node onto the stack.
Repeat this process for each node in the preorder string.
The first node created (the root) might not be on the stack anymore at the end, so remember the first node you created, which represents the root of the reconstructed tree.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def recover_from_preorder(traversal_string: str) -> TreeNode:
    node_stack = []
    index = 0
    root_node = None

    while index < len(traversal_string):
        depth = 0
        # Determine depth by counting leading dashes
        while index < len(traversal_string) and traversal_string[index] == '-':
            depth += 1
            index += 1

        node_value = ""
        # Extract node value
        while index < len(traversal_string) and traversal_string[index] != '-':
            node_value += traversal_string[index]
            index += 1

        current_node = TreeNode(int(node_value))

        # Adjust stack to find the correct parent
        while node_stack and depth <= len(node_stack) - 1:
            node_stack.pop()

        # Assign node to parent
        if node_stack:
            parent_node = node_stack[-1]
            if not parent_node.left:
                parent_node.left = current_node
            else:
                parent_node.right = current_node
        # Keep track of root node
        elif not root_node:
            root_node = current_node

        node_stack.append(current_node)

    return root_node

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the preorder string once, processing each node. For each node, the depth is determined, and the while loop pops elements from the stack. Crucially, each node is pushed onto the stack and popped at most once. Therefore, the total number of stack operations across all nodes is also proportional to n. Since all other operations within the loop (node creation, linking) take constant time, the overall time complexity is driven by the single pass through the input, making it O(n).

Space Complexity

O(W) – The algorithm uses a stack to store potential parent nodes. In the worst-case scenario, the stack could contain all nodes at a particular level of the tree, where W is the maximum width of the tree. Therefore, the auxiliary space used by the stack is proportional to the maximum width of the tree, W. Although N represents the number of nodes in the tree from the preorder traversal, the space needed is determined by the tree's shape, specifically the maximum width.

Edge Cases

Case	How to Handle
Null or empty input string	Return null, as there's no tree to reconstruct.
String contains only dashes	Return null, since there is no node value to create.
String starts with a non-zero number of dashes followed by a single digit	Create root node at depth based on leading dashes
Consecutive nodes at the same depth	Correctly creates siblings by backtracking to the correct parent node.
Input string represents a highly unbalanced tree (e.g., all left children)	The algorithm should correctly build the unbalanced structure, depth-first.
Input string representing a complete binary tree	The algorithm builds a fully balanced tree
Malformed input: more than one digit or non-digit characters besides dashes	Handle errors by returning null or throwing exception in the case of invalid input.
Deeply nested tree causing stack overflow in recursive implementation	Consider converting to iterative implementation if maximum depth can exceed the stack size, possibly employing a stack data structure.

Null or empty input string

How to Handle:

Return null, as there's no tree to reconstruct.

String contains only dashes

How to Handle:

Return null, since there is no node value to create.

String starts with a non-zero number of dashes followed by a single digit

How to Handle:

Create root node at depth based on leading dashes

Consecutive nodes at the same depth

How to Handle:

Correctly creates siblings by backtracking to the correct parent node.

Input string represents a highly unbalanced tree (e.g., all left children)

How to Handle:

The algorithm should correctly build the unbalanced structure, depth-first.

Input string representing a complete binary tree

How to Handle:

The algorithm builds a fully balanced tree

Malformed input: more than one digit or non-digit characters besides dashes

How to Handle:

Handle errors by returning null or throwing exception in the case of invalid input.

Deeply nested tree causing stack overflow in recursive implementation

How to Handle:

Consider converting to iterative implementation if maximum depth can exceed the stack size, possibly employing a stack data structure.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the `traversal` string, and what is the maximum depth of the binary tree?
Can the single-digit node values be zero?
Is the input `traversal` string always guaranteed to represent a valid preorder traversal of a binary tree, or should I handle cases where it's malformed?
If the input string is empty, should I return null, or is that considered an invalid input?
Are the number of dashes strictly indicative of the depth relative to the parent, or can there be gaps (e.g., '--1---2' where '2' should still be a child of '1')?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the first number in the traversal as the root of the tree.
Then, try all the possible ways to divide the remaining numbers into a left subtree and a right subtree.
For each of these divisions, treat the left subtree numbers as a separate, smaller problem and repeat the process: pick the first number as the root, and try all possible left/right splits within those numbers.
Do the same for the right subtree numbers.
Continue dividing and creating subtrees until you've used up all the numbers in the traversal.
Each time you build a complete tree structure, compare it to the original traversal order to see if it matches.
If a tree structure matches the given traversal, it is a valid solution. If multiple structures match, you can pick any one (or choose based on some criteria, if specified).
If you've exhausted all possible tree structures and none match, then there is no solution to the problem.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def recover_tree_brute_force(preorder):
    if not preorder:
        return None

    root_value = preorder[0]
    root = Node(root_value)

    if len(preorder) == 1:
        return root

    for i in range(len(preorder)):
        left_subtree_preorder = preorder[1:i+1]
        right_subtree_preorder = preorder[i+1:]

        # Recursively build left and right subtrees
        left_subtree = recover_tree_brute_force(left_subtree_preorder)
        
        right_subtree = recover_tree_brute_force(right_subtree_preorder)

        root.left = left_subtree
        root.right = right_subtree

        # Check if the generated tree's preorder matches the input
        if is_valid_tree(root, preorder):
            return root

        root.left = None
        root.right = None

    return None

def is_valid_tree(root, preorder):
    tree_preorder = generate_preorder(root)
    return tree_preorder == preorder

def generate_preorder(root):
    if not root:
        return []

    preorder_list = [root.value]
    preorder_list.extend(generate_preorder(root.left))
    preorder_list.extend(generate_preorder(root.right))
    return preorder_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin processing the preorder string from left to right, one node at a time.
For the current node, determine its depth by counting the number of dashes preceding its value.
While the stack isn't empty and the depth of the current node is less than or equal to the depth of the last node in the stack, remove the last node from the stack. This ensures we are always considering the correct parent for the current node.
Create a new node with the current value.
If the stack is not empty, the last node in the stack is the parent of the current node. Check if the parent node already has a left child. If not, the current node becomes the left child; otherwise, it becomes the right child.
Push the new node onto the stack.
Repeat this process for each node in the preorder string.
The first node created (the root) might not be on the stack anymore at the end, so remember the first node you created, which represents the root of the reconstructed tree.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def recover_from_preorder(traversal_string: str) -> TreeNode:
    node_stack = []
    index = 0
    root_node = None

    while index < len(traversal_string):
        depth = 0
        # Determine depth by counting leading dashes
        while index < len(traversal_string) and traversal_string[index] == '-':
            depth += 1
            index += 1

        node_value = ""
        # Extract node value
        while index < len(traversal_string) and traversal_string[index] != '-':
            node_value += traversal_string[index]
            index += 1

        current_node = TreeNode(int(node_value))

        # Adjust stack to find the correct parent
        while node_stack and depth <= len(node_stack) - 1:
            node_stack.pop()

        # Assign node to parent
        if node_stack:
            parent_node = node_stack[-1]
            if not parent_node.left:
                parent_node.left = current_node
            else:
                parent_node.right = current_node
        # Keep track of root node
        elif not root_node:
            root_node = current_node

        node_stack.append(current_node)

    return root_node

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return null, as there's no tree to reconstruct.
String contains only dashes	Return null, since there is no node value to create.
String starts with a non-zero number of dashes followed by a single digit	Create root node at depth based on leading dashes
Consecutive nodes at the same depth	Correctly creates siblings by backtracking to the correct parent node.
Input string represents a highly unbalanced tree (e.g., all left children)	The algorithm should correctly build the unbalanced structure, depth-first.
Input string representing a complete binary tree	The algorithm builds a fully balanced tree
Malformed input: more than one digit or non-digit characters besides dashes	Handle errors by returning null or throwing exception in the case of invalid input.
Deeply nested tree causing stack overflow in recursive implementation	Consider converting to iterative implementation if maximum depth can exceed the stack size, possibly employing a stack data structure.

Null or empty input string

How to Handle:

Return null, as there's no tree to reconstruct.

String contains only dashes

How to Handle:

Return null, since there is no node value to create.

String starts with a non-zero number of dashes followed by a single digit

How to Handle:

Create root node at depth based on leading dashes

Consecutive nodes at the same depth

How to Handle:

Correctly creates siblings by backtracking to the correct parent node.

Input string represents a highly unbalanced tree (e.g., all left children)

How to Handle:

The algorithm should correctly build the unbalanced structure, depth-first.

Input string representing a complete binary tree

How to Handle:

The algorithm builds a fully balanced tree

Malformed input: more than one digit or non-digit characters besides dashes

How to Handle:

Handle errors by returning null or throwing exception in the case of invalid input.

Deeply nested tree causing stack overflow in recursive implementation

How to Handle:

Consider converting to iterative implementation if maximum depth can exceed the stack size, possibly employing a stack data structure.