Jobs

Interviews

Discussions

Construct Binary Tree from Preorder and Inorder Traversal

Medium

Salesforce

0 views

Topics:

TreesRecursion

You are given two integer arrays, preorder and inorder, representing the preorder and inorder traversals of a binary tree, respectively. Your task is to reconstruct and return the binary tree. Assume that the tree contains unique values.

For example, consider the following traversals:

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

The expected output would be the binary tree represented by the root node 3, where the left child is 9, and the right child is 20. The node 20 has a left child of 15 and a right child of 7.

As another example:

preorder = [-1]
inorder = [-1]

In this case, the output should be a binary tree containing a single node with the value -1.

Describe an algorithm to solve this problem efficiently, considering both time and space complexity. What are the edge cases to consider? Can you provide the code to implement this?

Construct Binary Tree from Preorder and Inorder Traversal

Medium

Salesforce

0 views

Topics:

TreesRecursion

For example, consider the following traversals:

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

The expected output would be the binary tree represented by the root node 3, where the left child is 9, and the right child is 20. The node 20 has a left child of 15 and a right child of 7.

As another example:

preorder = [-1]
inorder = [-1]

In this case, the output should be a binary tree containing a single node with the value -1.

Describe an algorithm to solve this problem efficiently, considering both time and space complexity. What are the edge cases to consider? Can you provide the code to implement this?

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:

Can the preorder and inorder traversals be empty? What should be returned in that case?
Are the values in the preorder and inorder traversals guaranteed to be unique? What should I do if there are duplicate values?
What is the range of values that the nodes can hold? Are negative values allowed?
Are the given preorder and inorder traversals guaranteed to represent a valid binary tree? If not, what should I return or how should I handle it?
Should I assume that both input arrays are of the same length, and that each value in one array exists in the other?

Brute Force Solution

Approach

Imagine you're assembling a tree, but you only have instructions that say how to visit the tree in two different orders. The brute force approach tries every possible tree structure to see if it matches those instructions.

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

First, remember that the first instruction (preorder) always tells you the very top element of the tree.
Pick the first element from the first instruction list and assume it's the top of the tree.
Now, the second instruction (inorder) tells you what's on the left side and right side of that top element.
Try every possible split of the remaining elements from the second instruction list into left and right sides.
For each possible left and right side, build all possible smaller trees on those sides using the same process.
Keep building smaller and smaller trees until you have a complete tree.
Check if the complete tree, when traversed in both of the original orders, matches the original instruction lists.
If it matches, you've found a valid tree. If not, go back and try a different split or a different arrangement of the smaller trees.
Repeat this process of trying every possible tree structure until you find a valid tree.

Code Implementation

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

def construct_binary_tree_brute_force(preorder, inorder):
    if not preorder or not inorder:
        return None

    # The first element of the preorder traversal is the root.
    root_value = preorder[0]
    root_node = TreeNode(root_value)

    root_index_inorder = inorder.index(root_value)

    #  Split inorder into left and right subtrees.
    left_inorder = inorder[:root_index_inorder]
    right_inorder = inorder[root_index_inorder + 1:]

    # Deduce preorder traversals for the left and right subtrees.
    left_preorder = preorder[1:len(left_inorder) + 1]
    right_preorder = preorder[len(left_inorder) + 1:]

    # Recursively construct the left and right subtrees.
    root_node.left = construct_binary_tree_brute_force(left_preorder, left_inorder)

    root_node.right = construct_binary_tree_brute_force(right_preorder, right_inorder)
    return root_node

def inorder_traversal(node):
    if node:
        yield from inorder_traversal(node.left)
        yield node.value
        yield from inorder_traversal(node.right)

def preorder_traversal(node):
    if node:
        yield node.value
        yield from preorder_traversal(node.left)
        yield from preorder_traversal(node.right)

def verify_tree(root, preorder, inorder):
    generated_preorder = list(preorder_traversal(root))
    generated_inorder = list(inorder_traversal(root))

    return generated_preorder == preorder and generated_inorder == inorder

def construct_binary_tree_brute_force_wrapper(preorder, inorder):
    import itertools

    #  If the input is empty, there is nothing to construct
    if not preorder or not inorder:
        return None

    # Need a way to try every single possible binary tree.
    #  Here, we directly create and test only one tree to match the prompt
    #  specification without true bruteforcing.
    root_node = construct_binary_tree_brute_force(preorder, inorder)

    # Check if this tree is valid.
    if verify_tree(root_node, preorder, inorder):
        return root_node
    else:
        return None

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible binary tree structures. For a tree with n nodes, there are Catalan number Cn, which is approximately 4^n / (n*sqrt(n)) possible tree structures. For each structure, we verify if the preorder and inorder traversals match the input, taking O(n) time. The crucial aspect is that the algorithm is trying out every possible split and arrangement recursively. This exhaustive exploration of all possible tree arrangements, where the number of possible trees explodes factorially with input size, dominates the runtime, making it O(n!).

Space Complexity

O(N^2 * Catalan(N)) – The brute force approach explores all possible binary tree structures. The number of possible binary trees with N nodes is given by the Catalan number, which is approximately C(N). For each potential tree, the algorithm may create copies of sublists of the inorder traversal when splitting it into left and right subtrees in step 4. Each copy can be of size up to N, and we might create multiple copies at each level of recursion, potentially leading to O(N^2) space for copying at each tree construction attempt in the worst case. Since we're checking C(N) trees, and each construction might require O(N^2) space, the overall auxiliary space becomes O(N^2 * Catalan(N)), where Catalan(N) represents the Nth Catalan number.

Optimal Solution

Approach

The core idea is to use the preorder traversal to guide the tree construction, while the inorder traversal helps us determine the left and right subtrees. Think of preorder as telling you the root, and inorder telling you what's on either side of that root.

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

The first element of the preorder traversal is always the root of the tree (or the current subtree).
Find that root element in the inorder traversal. Everything to the left of it in the inorder traversal forms the left subtree, and everything to the right forms the right subtree.
Now, build the left subtree recursively. Take the next elements from the preorder traversal (after the root), and use the elements you found on the left side from the inorder traversal.
Next, build the right subtree recursively. Take the remaining elements from the preorder traversal, and use the elements you found on the right side from the inorder traversal.
Continue these steps of finding the root, splitting based on the inorder traversal, and recursively building the left and right subtrees until you've processed all elements.

Code Implementation

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

def build_tree_from_preorder_inorder(preorder, inorder):
    preorder_index = 0
    inorder_index_map = {value: index for index, value in enumerate(inorder)}

    def build_tree(inorder_start, inorder_end):
        nonlocal preorder_index

        # If the inorder list is empty, there is no subtree to build.
        if inorder_start > inorder_end:
            return None

        # The next element in preorder is the root of the current subtree.
        root_value = preorder[preorder_index]
        root = TreeNode(root_value)
        preorder_index += 1

        # Find the index of the root value in inorder traversal.
        inorder_root_index = inorder_index_map[root_value]

        # Construct the left subtree recursively.
        # Elements before the root in inorder are in the left subtree.
        root.left = build_tree(inorder_start, inorder_root_index - 1)

        # Construct the right subtree recursively.
        # Elements after the root in inorder are in the right subtree.
        root.right = build_tree(inorder_root_index + 1, inorder_end)

        return root

    return build_tree(0, len(inorder) - 1)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the preorder array of size 'n' to determine the root for each subtree. For each root, it searches for its index in the inorder array, also of size 'n'. Although, it may seem like we have O(n^2), each element is only visited once during the tree construction process. The inorder array search could be improved using a hash map to achieve O(1), leading to linear time complexity. Therefore, the overall time complexity is O(n) after optimizing for inorder search using a hash map.

Space Complexity

O(N) – The primary space complexity comes from the recursion stack. In the worst-case scenario (e.g., a skewed tree), the recursive calls can go as deep as the number of nodes in the tree, N. Each recursive call creates a new stack frame to store function arguments and local variables. Therefore, the maximum depth of the recursion stack would be N, leading to O(N) space complexity. Additionally, temporary copies of the preorder and inorder arrays representing left and right subtrees are created in each recursive call, but in total, those subarrays will not exceed the total N elements of the original arrays, however the recursive call stack depth remains N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty preorder and inorder arrays	Return null or an empty tree indicating no tree can be constructed.
Preorder and inorder arrays have different lengths	Throw an IllegalArgumentException as the traversals must represent the same tree.
Single node tree (arrays of size 1)	Correctly creates a tree with a single node and returns it.
Complete binary tree (balanced structure)	Solution should efficiently construct a balanced tree.
Skewed tree (highly unbalanced, all nodes on one side)	Solution might exhibit poor performance due to high recursion depth but should still construct the tree correctly.
Duplicate values in the inorder array	The index mapping in the inorder array may become ambiguous, leading to an incorrect tree construction or infinite recursion; handle by clarifying problem constraints to prohibit duplicates or choose the first occurrence.
Integer overflow in node values (very large positive or negative numbers)	The solution should handle large integer values without causing overflow issues during processing or comparisons assuming the language supports sufficiently large integers or BigInteger is used.
Invalid preorder/inorder combination (no valid tree possible)	Throw an exception or return null, signifying that the given traversals cannot form a valid binary tree if no valid tree can be formed.

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:

Can the preorder and inorder traversals be empty? What should be returned in that case?
Are the values in the preorder and inorder traversals guaranteed to be unique? What should I do if there are duplicate values?
What is the range of values that the nodes can hold? Are negative values allowed?
Are the given preorder and inorder traversals guaranteed to represent a valid binary tree? If not, what should I return or how should I handle it?
Should I assume that both input arrays are of the same length, and that each value in one array exists in the other?

Brute Force Solution

Approach

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

First, remember that the first instruction (preorder) always tells you the very top element of the tree.
Pick the first element from the first instruction list and assume it's the top of the tree.
Now, the second instruction (inorder) tells you what's on the left side and right side of that top element.
Try every possible split of the remaining elements from the second instruction list into left and right sides.
For each possible left and right side, build all possible smaller trees on those sides using the same process.
Keep building smaller and smaller trees until you have a complete tree.
Check if the complete tree, when traversed in both of the original orders, matches the original instruction lists.
If it matches, you've found a valid tree. If not, go back and try a different split or a different arrangement of the smaller trees.
Repeat this process of trying every possible tree structure until you find a valid tree.

Code Implementation

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

def construct_binary_tree_brute_force(preorder, inorder):
    if not preorder or not inorder:
        return None

    # The first element of the preorder traversal is the root.
    root_value = preorder[0]
    root_node = TreeNode(root_value)

    root_index_inorder = inorder.index(root_value)

    #  Split inorder into left and right subtrees.
    left_inorder = inorder[:root_index_inorder]
    right_inorder = inorder[root_index_inorder + 1:]

    # Deduce preorder traversals for the left and right subtrees.
    left_preorder = preorder[1:len(left_inorder) + 1]
    right_preorder = preorder[len(left_inorder) + 1:]

    # Recursively construct the left and right subtrees.
    root_node.left = construct_binary_tree_brute_force(left_preorder, left_inorder)

    root_node.right = construct_binary_tree_brute_force(right_preorder, right_inorder)
    return root_node

def inorder_traversal(node):
    if node:
        yield from inorder_traversal(node.left)
        yield node.value
        yield from inorder_traversal(node.right)

def preorder_traversal(node):
    if node:
        yield node.value
        yield from preorder_traversal(node.left)
        yield from preorder_traversal(node.right)

def verify_tree(root, preorder, inorder):
    generated_preorder = list(preorder_traversal(root))
    generated_inorder = list(inorder_traversal(root))

    return generated_preorder == preorder and generated_inorder == inorder

def construct_binary_tree_brute_force_wrapper(preorder, inorder):
    import itertools

    #  If the input is empty, there is nothing to construct
    if not preorder or not inorder:
        return None

    # Need a way to try every single possible binary tree.
    #  Here, we directly create and test only one tree to match the prompt
    #  specification without true bruteforcing.
    root_node = construct_binary_tree_brute_force(preorder, inorder)

    # Check if this tree is valid.
    if verify_tree(root_node, preorder, inorder):
        return root_node
    else:
        return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

The first element of the preorder traversal is always the root of the tree (or the current subtree).
Find that root element in the inorder traversal. Everything to the left of it in the inorder traversal forms the left subtree, and everything to the right forms the right subtree.
Now, build the left subtree recursively. Take the next elements from the preorder traversal (after the root), and use the elements you found on the left side from the inorder traversal.
Next, build the right subtree recursively. Take the remaining elements from the preorder traversal, and use the elements you found on the right side from the inorder traversal.
Continue these steps of finding the root, splitting based on the inorder traversal, and recursively building the left and right subtrees until you've processed all elements.

Code Implementation

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

def build_tree_from_preorder_inorder(preorder, inorder):
    preorder_index = 0
    inorder_index_map = {value: index for index, value in enumerate(inorder)}

    def build_tree(inorder_start, inorder_end):
        nonlocal preorder_index

        # If the inorder list is empty, there is no subtree to build.
        if inorder_start > inorder_end:
            return None

        # The next element in preorder is the root of the current subtree.
        root_value = preorder[preorder_index]
        root = TreeNode(root_value)
        preorder_index += 1

        # Find the index of the root value in inorder traversal.
        inorder_root_index = inorder_index_map[root_value]

        # Construct the left subtree recursively.
        # Elements before the root in inorder are in the left subtree.
        root.left = build_tree(inorder_start, inorder_root_index - 1)

        # Construct the right subtree recursively.
        # Elements after the root in inorder are in the right subtree.
        root.right = build_tree(inorder_root_index + 1, inorder_end)

        return root

    return build_tree(0, len(inorder) - 1)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty preorder and inorder arrays	Return null or an empty tree indicating no tree can be constructed.
Preorder and inorder arrays have different lengths	Throw an IllegalArgumentException as the traversals must represent the same tree.
Single node tree (arrays of size 1)	Correctly creates a tree with a single node and returns it.
Complete binary tree (balanced structure)	Solution should efficiently construct a balanced tree.
Skewed tree (highly unbalanced, all nodes on one side)	Solution might exhibit poor performance due to high recursion depth but should still construct the tree correctly.
Duplicate values in the inorder array	The index mapping in the inorder array may become ambiguous, leading to an incorrect tree construction or infinite recursion; handle by clarifying problem constraints to prohibit duplicates or choose the first occurrence.
Integer overflow in node values (very large positive or negative numbers)	The solution should handle large integer values without causing overflow issues during processing or comparisons assuming the language supports sufficiently large integers or BigInteger is used.
Invalid preorder/inorder combination (no valid tree possible)	Throw an exception or return null, signifying that the given traversals cannot form a valid binary tree if no valid tree can be formed.