Jobs

Interviews

Discussions

Construct Binary Tree from Inorder and Postorder Traversal

Medium

Apple

2 views

Topics:

TreesRecursion

Given two integer arrays, inorder and postorder, representing the inorder and postorder traversals of a binary tree, respectively, construct and return the binary tree. Assume that both arrays contain unique elements and that postorder corresponds to the postorder traversal and inorder is the inorder traversal of the same tree.

For example:

If inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3], the expected output is a binary tree with the structure:
```
    3
   / \
  9  20
     /  \
    15   7
```
If inorder = [-1] and postorder = [-1], the expected output is a binary tree with a single node: -1.

Clarify your assumptions about the input, especially regarding empty inputs, the presence of duplicate values, and the guaranteed validity of the traversals.

How would you approach constructing the binary tree from these traversals? Can you describe a step-by-step algorithm? What are the time and space complexity considerations for your approach? Consider edge cases such as empty arrays or arrays representing a single node tree.

Construct Binary Tree from Inorder and Postorder Traversal

Medium

Apple

2 views

Topics:

TreesRecursion

For example:

If inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3], the expected output is a binary tree with the structure:
```
    3
   / \
  9  20
     /  \
    15   7
```
If inorder = [-1] and postorder = [-1], the expected output is a binary tree with a single node: -1.

Clarify your assumptions about the input, especially regarding empty inputs, the presence of duplicate values, and the guaranteed validity of the traversals.

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 binary tree contain duplicate values, and if so, how should I handle them during construction?
What should I return if either the inorder or postorder traversal is empty or null?
Are the values in the inorder and postorder traversals guaranteed to be unique, and are they of type integer?
Is it guaranteed that the given inorder and postorder traversals represent a valid binary tree, or do I need to validate this?
What is the expected size of the tree (number of nodes), and are there any memory constraints I should consider?

Brute Force Solution

Approach

We need to build a tree using two lists that tell us how to visit the nodes: one goes in order (left, root, right) and the other goes root last (left, right, root). The brute force method tries every single possible tree structure that matches these visit orders, until it finds the correct one.

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

Consider all the ways to pick the very top node (the root) from the 'root last' list. Each choice gives you a different possible tree.
Once you pick a root, the 'in order' list tells you which nodes are on the left side of the root and which are on the right side.
For each side, try all possible ways to pick the top node (root) of that smaller tree from the 'root last' list. This splits each side into even smaller pieces.
Keep repeating this process of picking a root and splitting the tree into left and right sides, until you're left with only single nodes.
For each fully built tree you create in this way, check if going through it using 'in order' and 'root last' gives you the same lists you started with.
If a tree doesn't match the original lists, discard it and try another possible tree.
Keep building trees and checking them until you find one that matches both the 'in order' and 'root last' lists. That's your answer!

Code Implementation

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

def construct_binary_tree_brute_force(inorder, postorder):

    def build_tree(inorder_list, postorder_list):
        # If either list is empty, there's no tree to build.
        if not inorder_list or not postorder_list:
            return None

        # Last element in postorder is always the root.
        root_value = postorder_list[-1]
        root_node = TreeNode(root_value)

        root_index_inorder = inorder_list.index(root_value)

        # Divide inorder list to left and right subtrees.
        left_inorder = inorder_list[:root_index_inorder]
        right_inorder = inorder_list[root_index_inorder + 1:]

        # Calculate the sizes of left and right subtrees for postorder.
        left_size = len(left_inorder)

        # Construct the left and right postorder sublists.
        left_postorder = postorder_list[:left_size]
        right_postorder = postorder_list[left_size:-1]

        root_node.left = build_tree(left_inorder, left_postorder)
        root_node.right = build_tree(right_inorder, right_postorder)

        return root_node

    def inorder_traversal(root):
        if root:
            return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)
        return []

    def postorder_traversal(root):
        if root:
            return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value]
        return []

    def verify_tree(possible_root):
        # Generate traversals from the constructed tree
        inorder_result = inorder_traversal(possible_root)
        postorder_result = postorder_traversal(possible_root)

        # Compare with the original traversals
        return inorder_result == inorder and postorder_result == postorder

    import itertools

    # Generate all possible permutations for root selection
    possible_trees = []

    def generate_trees(inorder_list, postorder_list):
        if not inorder_list:
            return [None]
        
        trees = []
        for i in range(len(postorder_list)):
            root_value = postorder_list[i]
            root_index_inorder = inorder_list.index(root_value)
            left_inorder = inorder_list[:root_index_inorder]
            right_inorder = inorder_list[root_index_inorder+1:]
            left_postorder = postorder_list[:i]
            right_postorder = postorder_list[i:-1]

            # Recursively build the left and right subtrees
            left_trees = generate_trees(left_inorder, left_postorder)
            right_trees = generate_trees(right_inorder, right_postorder)

            # Combine each possible left and right subtree with the current root
            for left_tree in left_trees:
                for right_tree in right_trees:
                    root_node = TreeNode(root_value)
                    root_node.left = left_tree
                    root_node.right = right_tree
                    trees.append(root_node)
        return trees

    all_possible_trees = generate_trees(inorder, postorder)

    # Check each possible tree until we find the correct one
    for possible_root in all_possible_trees:
        if verify_tree(possible_root):
            return possible_root

    return None

Big(O) Analysis

Time Complexity

O(n^n) – The brute force method explores all possible binary tree structures. In the worst-case, the algorithm tries every possible combination of root nodes, which leads to exploring a vast number of tree structures. For a tree with n nodes, there can be up to n choices for the root, and then recursively n choices for roots of subtrees on both sides, which leads to an n-ary tree search where each node potentially has n children. Each fully constructed tree needs to be validated against the inorder and postorder traversals, contributing a further factor of O(n) for traversal comparison, although this is dominated by the structure generation. The number of possible tree structures grows as a function close to Catalan numbers, which is super-polynomial, but as the explanation details exploring every tree structure from root selection and validating it, this leads to an extremely high runtime on the order of O(n^n).

Space Complexity

O(N^2 * Catalan(N)) – The brute force approach explores all possible binary tree structures. Building each potential tree requires storing nodes, potentially leading to a tree representation with N nodes, where N is the number of nodes in the inorder/postorder traversals. For each fully constructed tree, we store the inorder and postorder traversals to verify its correctness, requiring O(N) space each. The number of possible binary trees with N nodes is given by the Catalan number, Catalan(N), and for each tree of size N, we might store N nodes for the tree itself plus potentially additional space for comparisons, leading to a total space of roughly N * Catalan(N) for all valid trees. Because we keep trying every single possible tree structure, this is multiplied by the complexity of generating these, ultimately resulting in O(N^2 * Catalan(N)) where the N^2 comes from the tree construction.

Optimal Solution

Approach

We can build the tree without guesswork by leveraging the properties of inorder and postorder traversals. The last element in the postorder traversal is always the root of the (sub)tree. We can use this root to split the inorder traversal into left and right subtrees, and then recursively apply the same logic to build the entire tree.

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

The very last value we see in the postorder list gives us the root of the entire tree.
Find that root value within the inorder list. This splits the inorder list into two smaller lists: everything to the left of the root (the left subtree), and everything to the right of the root (the right subtree).
Now, figure out what section of the postorder list relates to the left subtree and the right subtree by counting elements in the inorder subtrees.
Create a new tree node using the root value we identified.
Recursively build the left subtree by applying steps 1-4 using the relevant section of the postorder list and the left portion of the inorder list.
Recursively build the right subtree by applying steps 1-4 using the relevant section of the postorder list and the right portion of the inorder list.
Attach the left and right subtrees we built to the root node.
Continue the recursion until all values have been used to construct the whole tree.

Code Implementation

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

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None

    # The last element of postorder is the root
    root_value = postorder[-1]
    root = TreeNode(root_value)

    # Find the index of the root in inorder list
    root_index_inorder = inorder.index(root_value)

    # Calculate sizes of left and right subtrees
    left_subtree_size = root_index_inorder

    # Recursively build the left subtree
    root.left = buildTree(
        inorder[:left_subtree_size],
        postorder[:left_subtree_size]
    )

    # Recursively build the right subtree.
    # postorder[left_subtree_size:-1] selects the postorder traversal for the right subtree.
    root.right = buildTree(
        inorder[root_index_inorder + 1:],
        postorder[left_subtree_size:-1]
    )

    return root

Big(O) Analysis

Time Complexity

O(n) – The time complexity is driven by the recursive tree construction. In the worst-case scenario, where the tree is highly unbalanced (e.g., a skewed tree), for each node we identify the root in the inorder array. Finding the root in the inorder array using a linear scan takes O(n) in the worst case, however, if we pre-compute an inorder map, this becomes O(1). Each node is visited only once while splitting into left and right subtrees. Therefore, the overall time complexity is O(n) where n is the number of nodes.

Space Complexity

O(N) – The primary driver of auxiliary space is the recursion depth, which can reach N in the worst-case scenario of a skewed tree, where N is the number of nodes. Each recursive call adds a new frame to the call stack, consuming memory. In addition to the call stack, in each recursive step, sublists of the inorder and postorder traversals may be created, potentially using O(N) space cumulatively over all calls. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty inorder and postorder arrays	Return null (or equivalent representation of an empty tree) since there's no tree to construct.
Inorder and postorder arrays of different lengths	Throw an exception or return null, indicating an invalid input, as tree construction is impossible.
Single node tree (arrays with one element)	Create a single node tree with the value from the single element and return it.
Skewed tree (e.g., only left or only right children)	The recursive algorithm should handle skewed trees correctly as the index manipulation ensures proper left/right subtree construction.
Duplicate values in the inorder array	The algorithm should still correctly build the tree if duplicate values exist in the inorder array, albeit with potentially non-unique tree structure.
Large tree depth causing stack overflow (if using recursion)	Consider iterative approach with explicit stack to avoid potential stack overflow errors for very deep trees.
Input arrays contain negative or zero values	The algorithm should function correctly with negative or zero values as node values are generally treated as data regardless of their sign.
Postorder does not represent the traversal of the inorder tree	The algorithm will likely return a malformed tree or get stuck in an infinite loop; input validation for consistency should be included.

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 binary tree contain duplicate values, and if so, how should I handle them during construction?
What should I return if either the inorder or postorder traversal is empty or null?
Are the values in the inorder and postorder traversals guaranteed to be unique, and are they of type integer?
Is it guaranteed that the given inorder and postorder traversals represent a valid binary tree, or do I need to validate this?
What is the expected size of the tree (number of nodes), and are there any memory constraints I should consider?

Brute Force Solution

Approach

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

Consider all the ways to pick the very top node (the root) from the 'root last' list. Each choice gives you a different possible tree.
Once you pick a root, the 'in order' list tells you which nodes are on the left side of the root and which are on the right side.
For each side, try all possible ways to pick the top node (root) of that smaller tree from the 'root last' list. This splits each side into even smaller pieces.
Keep repeating this process of picking a root and splitting the tree into left and right sides, until you're left with only single nodes.
For each fully built tree you create in this way, check if going through it using 'in order' and 'root last' gives you the same lists you started with.
If a tree doesn't match the original lists, discard it and try another possible tree.
Keep building trees and checking them until you find one that matches both the 'in order' and 'root last' lists. That's your answer!

Code Implementation

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

def construct_binary_tree_brute_force(inorder, postorder):

    def build_tree(inorder_list, postorder_list):
        # If either list is empty, there's no tree to build.
        if not inorder_list or not postorder_list:
            return None

        # Last element in postorder is always the root.
        root_value = postorder_list[-1]
        root_node = TreeNode(root_value)

        root_index_inorder = inorder_list.index(root_value)

        # Divide inorder list to left and right subtrees.
        left_inorder = inorder_list[:root_index_inorder]
        right_inorder = inorder_list[root_index_inorder + 1:]

        # Calculate the sizes of left and right subtrees for postorder.
        left_size = len(left_inorder)

        # Construct the left and right postorder sublists.
        left_postorder = postorder_list[:left_size]
        right_postorder = postorder_list[left_size:-1]

        root_node.left = build_tree(left_inorder, left_postorder)
        root_node.right = build_tree(right_inorder, right_postorder)

        return root_node

    def inorder_traversal(root):
        if root:
            return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)
        return []

    def postorder_traversal(root):
        if root:
            return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value]
        return []

    def verify_tree(possible_root):
        # Generate traversals from the constructed tree
        inorder_result = inorder_traversal(possible_root)
        postorder_result = postorder_traversal(possible_root)

        # Compare with the original traversals
        return inorder_result == inorder and postorder_result == postorder

    import itertools

    # Generate all possible permutations for root selection
    possible_trees = []

    def generate_trees(inorder_list, postorder_list):
        if not inorder_list:
            return [None]
        
        trees = []
        for i in range(len(postorder_list)):
            root_value = postorder_list[i]
            root_index_inorder = inorder_list.index(root_value)
            left_inorder = inorder_list[:root_index_inorder]
            right_inorder = inorder_list[root_index_inorder+1:]
            left_postorder = postorder_list[:i]
            right_postorder = postorder_list[i:-1]

            # Recursively build the left and right subtrees
            left_trees = generate_trees(left_inorder, left_postorder)
            right_trees = generate_trees(right_inorder, right_postorder)

            # Combine each possible left and right subtree with the current root
            for left_tree in left_trees:
                for right_tree in right_trees:
                    root_node = TreeNode(root_value)
                    root_node.left = left_tree
                    root_node.right = right_tree
                    trees.append(root_node)
        return trees

    all_possible_trees = generate_trees(inorder, postorder)

    # Check each possible tree until we find the correct one
    for possible_root in all_possible_trees:
        if verify_tree(possible_root):
            return possible_root

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

The very last value we see in the postorder list gives us the root of the entire tree.
Find that root value within the inorder list. This splits the inorder list into two smaller lists: everything to the left of the root (the left subtree), and everything to the right of the root (the right subtree).
Now, figure out what section of the postorder list relates to the left subtree and the right subtree by counting elements in the inorder subtrees.
Create a new tree node using the root value we identified.
Recursively build the left subtree by applying steps 1-4 using the relevant section of the postorder list and the left portion of the inorder list.
Recursively build the right subtree by applying steps 1-4 using the relevant section of the postorder list and the right portion of the inorder list.
Attach the left and right subtrees we built to the root node.
Continue the recursion until all values have been used to construct the whole tree.

Code Implementation

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

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None

    # The last element of postorder is the root
    root_value = postorder[-1]
    root = TreeNode(root_value)

    # Find the index of the root in inorder list
    root_index_inorder = inorder.index(root_value)

    # Calculate sizes of left and right subtrees
    left_subtree_size = root_index_inorder

    # Recursively build the left subtree
    root.left = buildTree(
        inorder[:left_subtree_size],
        postorder[:left_subtree_size]
    )

    # Recursively build the right subtree.
    # postorder[left_subtree_size:-1] selects the postorder traversal for the right subtree.
    root.right = buildTree(
        inorder[root_index_inorder + 1:],
        postorder[left_subtree_size:-1]
    )

    return root

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty inorder and postorder arrays	Return null (or equivalent representation of an empty tree) since there's no tree to construct.
Inorder and postorder arrays of different lengths	Throw an exception or return null, indicating an invalid input, as tree construction is impossible.
Single node tree (arrays with one element)	Create a single node tree with the value from the single element and return it.
Skewed tree (e.g., only left or only right children)	The recursive algorithm should handle skewed trees correctly as the index manipulation ensures proper left/right subtree construction.
Duplicate values in the inorder array	The algorithm should still correctly build the tree if duplicate values exist in the inorder array, albeit with potentially non-unique tree structure.
Large tree depth causing stack overflow (if using recursion)	Consider iterative approach with explicit stack to avoid potential stack overflow errors for very deep trees.
Input arrays contain negative or zero values	The algorithm should function correctly with negative or zero values as node values are generally treated as data regardless of their sign.
Postorder does not represent the traversal of the inorder tree	The algorithm will likely return a malformed tree or get stuck in an infinite loop; input validation for consistency should be included.