Jobs

Interviews

Discussions

Construct Binary Tree from Preorder and Postorder Traversal

Medium

Google

3 views

Topics:

TreesRecursion

You are given two integer arrays, preorder and postorder, representing the preorder and postorder traversals of a binary tree with distinct values. Your task is to reconstruct and return the binary tree.

If multiple valid binary trees can be constructed from the given traversals, you can return any one of them.

Example 1:

preorder = [1, 2, 4, 5, 3, 6, 7] postorder = [4, 5, 2, 6, 7, 3, 1]

Construct the binary tree represented by these traversals. The output should be the root node of the constructed tree, which when traversed in-order, could yield [4,2,5,1,6,3,7].

Example 2:

preorder = [1] postorder = [1]

In this case, the binary tree simply consists of a single node with the value 1. Return a TreeNode representing this node.

Constraints:

The lengths of preorder and postorder are between 1 and 30, inclusive.
The values in preorder and postorder are unique and within the range of 1 to the length of the arrays.
postorder.length == preorder.length

Write a function that takes the preorder and postorder arrays as input and returns the root node of the reconstructed binary tree.

Construct Binary Tree from Preorder and Postorder Traversal

Medium

Google

3 views

Topics:

TreesRecursion

If multiple valid binary trees can be constructed from the given traversals, you can return any one of them.

Example 1:

preorder = [1, 2, 4, 5, 3, 6, 7] postorder = [4, 5, 2, 6, 7, 3, 1]

Construct the binary tree represented by these traversals. The output should be the root node of the constructed tree, which when traversed in-order, could yield [4,2,5,1,6,3,7].

Example 2:

preorder = [1] postorder = [1]

In this case, the binary tree simply consists of a single node with the value 1. Return a TreeNode representing this node.

Constraints:

The lengths of preorder and postorder are between 1 and 30, inclusive.
The values in preorder and postorder are unique and within the range of 1 to the length of the arrays.
postorder.length == preorder.length

Write a function that takes the preorder and postorder arrays as input and returns the root node of the reconstructed binary tree.

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:

Are the values in the preorder and postorder traversals guaranteed to be distinct?
If the input arrays do not represent a valid binary tree construction (e.g., conflicting orderings), what should the function return (null/None, an empty tree, or throw an error)?
Can the input arrays be empty or null? If so, how should I handle those cases?
Are the input arrays guaranteed to have the same length, and if so, does that length correspond to the number of nodes in the tree?
Should the function return *any* valid binary tree that can be constructed from the traversals, or is there some specific criteria for which valid tree to construct if multiple are possible?

Brute Force Solution

Approach

The core idea of the brute force method is to explore every possible tree structure that could be formed using the given orderings. We build trees and check if they satisfy the given pre-order and post-order traversals. It is like trying all the different puzzle piece combinations until one fits.

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

Consider that the first element in the preorder traversal is always the root of the tree.
Now, look at the postorder traversal. The root is the last element there.
Try different ways to divide the remaining elements into the left and right subtrees.
For each possible division, build the corresponding left and right subtrees recursively using the same approach.
Once a tree is constructed, check if the pre-order and post-order traversal of the newly created tree matches the given pre-order and post-order traversals.
If the traversals do not match, discard the constructed tree and try a different division.
If the traversals match, we've found a valid tree. Store this tree. Repeat steps to find all possible valid trees.
If you need to find a unique tree you must have more information, or return any 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_traversal, postorder_traversal
):
    def build_tree(
        preorder_start,
        preorder_end,
        postorder_start,
        postorder_end,
    ):
        if preorder_start > preorder_end:
            return None

        root_value = preorder_traversal[preorder_start]
        root = TreeNode(root_value)

        # Base case: single node
        if preorder_start == preorder_end:
            return root

        # Find the index of the left subtree root in postorder
        left_subtree_root_value =
            preorder_traversal[preorder_start + 1]
        left_subtree_root_index =
            postorder_traversal.index(left_subtree_root_value)

        left_subtree_size =
            left_subtree_root_index - postorder_start + 1

        root.left = build_tree(
            preorder_start + 1,
            preorder_start + left_subtree_size,
            postorder_start,
            left_subtree_root_index,
        )

        root.right = build_tree(
            preorder_start + left_subtree_size + 1,
            preorder_end,
            left_subtree_root_index + 1,
            postorder_end - 1,
        )

        return root

    def check_traversal(root, preorder, postorder):
        preorder_result = []
        postorder_result = []

        def traverse(node):
            if not node:
                return

            preorder_result.append(node.value)
            traverse(node.left)
            traverse(node.right)
            postorder_result.append(node.value)

        traverse(root)

        # Postorder is constructed backwards, must reverse
        postorder_result.reverse()

        if preorder_result == preorder and \
           postorder_result == postorder:
            return True
        else:
            return False

    trees = []
    root = build_tree(0, len(preorder_traversal) - 1, 0, \
                len(postorder_traversal) - 1)

    # Verify if the constructed tree matches the given traversals
    if check_traversal(root, preorder_traversal, \
                       postorder_traversal):
        return root
    else:
        return None

# Example Usage:
# preorder = [1, 2, 4, 5, 3, 6, 7]
# postorder = [4, 5, 2, 6, 7, 3, 1]
# tree = construct_binary_tree_brute_force(preorder, postorder)
# print(tree)

Big(O) Analysis

Time Complexity

O(n^n) – The brute force approach explores all possible binary tree structures. For each node, we iterate through possible divisions of the remaining elements into left and right subtrees. In the worst-case scenario, we consider all possible binary tree shapes, which grows exponentially with the number of nodes (n). Since, in the worst case, constructing each tree and verifying its traversals requires O(n) time, and we explore a number of trees that grows as n to the power of n, the overall time complexity is approximately O(n^n).

Space Complexity

O(N^2) – The described brute force approach explores all possible tree structures through recursive calls. In the worst-case, the recursion depth can be proportional to N (the number of nodes), and at each level, we potentially create temporary sublists of preorder and postorder arrays for the left and right subtrees, potentially of size N at each level. Additionally, storing the created trees to check pre-order and post-order traversal will take O(N) per tree, and in the worst case, we might explore a large number of trees proportional to N, leading to a combined space for storing created trees and the recursion stack of at most O(N^2). Thus, the overall space complexity becomes O(N^2).

Optimal Solution

Approach

We're given two ways to walk through a tree and need to rebuild the tree structure. The trick is to use the order of these walks to figure out the 'who's in charge' relationship between different parts of the tree, and then build the tree piece by piece using that knowledge.

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

The very first thing we see when walking the tree in the preorder way tells us who the main boss of the entire tree is. That's the root.
Now that we know who the root is, we can look in the postorder walk to see which parts of the tree are its direct reports on the left and right sides.
The postorder walk tells us the left side's people first, then the right side's people, and lastly the root itself. This allows us to split up the rest of the nodes into left and right subtrees.
We now know the range of nodes which belong in the left and right branches. Think of it like slicing a big group into smaller teams.
Repeat the whole process again, but now focusing only on the left team, and then the right team. The first node in the preorder list of that team becomes the boss (root) of that team, and the postorder list tells you how to break up the team further.
Keep doing this until everyone is assigned to a tree node, and the tree is complete.

Code Implementation

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

def construct_from_preorder_postorder(preorder, postorder):
    preorder_index_tracker = 0

    def construct_tree(preorder_start, preorder_end, postorder_start, postorder_end):
        nonlocal preorder_index_tracker

        # If subarray is empty, there is nothing to construct
        if preorder_start > preorder_end:
            return None

        # First element of preorder is root of (sub)tree
        root_value = preorder[preorder_index_tracker]
        root_node = TreeNode(root_value)
        preorder_index_tracker += 1

        # If the (sub)tree has one element, return it
        if preorder_start == preorder_end:
            return root_node

        # Find root in postorder to determine left subtree size
        left_subtree_root_index_in_postorder = postorder.index(preorder[preorder_index_tracker])

        # Size of left subtree
        nodes_in_left_subtree = left_subtree_root_index_in_postorder - postorder_start + 1
        
        # Construct the left subtree
        root_node.left = construct_tree(
            preorder_index_tracker, preorder_index_tracker + nodes_in_left_subtree - 1,
            postorder_start, left_subtree_root_index_in_postorder
        )

        #Advance preorder index for right subtree construction
        preorder_index_tracker += nodes_in_left_subtree

        # Construct the right subtree
        root_node.right = construct_tree(
            preorder_index_tracker, preorder_end,
            left_subtree_root_index_in_postorder + 1, postorder_end - 1
        )
        # Return the constructed tree
        return root_node
    
    #Driver Function
    root = construct_tree(0, len(preorder) - 1, 0, len(postorder) - 1)
    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm's time complexity is primarily determined by the recursive calls made to construct the subtrees. In the worst-case scenario, each node in the preorder and postorder traversals needs to be processed to construct the tree. While we search for the index of the root's left child in the postorder array, the average time complexity of this search can be considered O(1) due to hashmaps. This results in a roughly linear traversal of the input arrays and the dominant operation is processing each of the n nodes, thus the algorithm has O(n) time complexity.

Space Complexity

O(N) – The dominant space complexity factor is the recursion depth. In the worst case (e.g., a skewed tree), the recursive calls to build subtrees will create a call stack of depth N, where N is the number of nodes in the tree. Each recursive call requires storing function arguments and local variables on the stack. While there aren't significant auxiliary data structures besides the call stack itself, the stack space grows linearly with N in the worst-case scenario, thus the space is O(N).

Edge Cases

Case	How to Handle
Empty preorder or postorder array	Return null, as an empty tree cannot be constructed.
Preorder and postorder arrays have different lengths	Throw an exception because a valid tree cannot be constructed from inconsistent traversals.
Preorder and postorder arrays contain different sets of values	Throw an exception as the tree structure cannot be consistent with both traversals.
Single element arrays	Create a single-node tree with the element as the root.
Arrays with two elements	Create a root node with the first element of preorder, and a left child with the second element (preorder[1] must equal postorder[0]).
All elements in the arrays are identical	The resulting tree will be a skewed tree, handled correctly by the recursive construction.
Large input arrays potentially leading to stack overflow due to deep recursion	Ensure your code is tail-recursive or consider transforming the recursive algorithm into an iterative one.
The given preorder and postorder traversals do not represent a valid binary tree	Return null (or throw an exception) if at any point the construction process violates the properties of preorder/postorder traversal.

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:

Are the values in the preorder and postorder traversals guaranteed to be distinct?
If the input arrays do not represent a valid binary tree construction (e.g., conflicting orderings), what should the function return (null/None, an empty tree, or throw an error)?
Can the input arrays be empty or null? If so, how should I handle those cases?
Are the input arrays guaranteed to have the same length, and if so, does that length correspond to the number of nodes in the tree?
Should the function return *any* valid binary tree that can be constructed from the traversals, or is there some specific criteria for which valid tree to construct if multiple are possible?

Brute Force Solution

Approach

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

Consider that the first element in the preorder traversal is always the root of the tree.
Now, look at the postorder traversal. The root is the last element there.
Try different ways to divide the remaining elements into the left and right subtrees.
For each possible division, build the corresponding left and right subtrees recursively using the same approach.
Once a tree is constructed, check if the pre-order and post-order traversal of the newly created tree matches the given pre-order and post-order traversals.
If the traversals do not match, discard the constructed tree and try a different division.
If the traversals match, we've found a valid tree. Store this tree. Repeat steps to find all possible valid trees.
If you need to find a unique tree you must have more information, or return any 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_traversal, postorder_traversal
):
    def build_tree(
        preorder_start,
        preorder_end,
        postorder_start,
        postorder_end,
    ):
        if preorder_start > preorder_end:
            return None

        root_value = preorder_traversal[preorder_start]
        root = TreeNode(root_value)

        # Base case: single node
        if preorder_start == preorder_end:
            return root

        # Find the index of the left subtree root in postorder
        left_subtree_root_value =
            preorder_traversal[preorder_start + 1]
        left_subtree_root_index =
            postorder_traversal.index(left_subtree_root_value)

        left_subtree_size =
            left_subtree_root_index - postorder_start + 1

        root.left = build_tree(
            preorder_start + 1,
            preorder_start + left_subtree_size,
            postorder_start,
            left_subtree_root_index,
        )

        root.right = build_tree(
            preorder_start + left_subtree_size + 1,
            preorder_end,
            left_subtree_root_index + 1,
            postorder_end - 1,
        )

        return root

    def check_traversal(root, preorder, postorder):
        preorder_result = []
        postorder_result = []

        def traverse(node):
            if not node:
                return

            preorder_result.append(node.value)
            traverse(node.left)
            traverse(node.right)
            postorder_result.append(node.value)

        traverse(root)

        # Postorder is constructed backwards, must reverse
        postorder_result.reverse()

        if preorder_result == preorder and \
           postorder_result == postorder:
            return True
        else:
            return False

    trees = []
    root = build_tree(0, len(preorder_traversal) - 1, 0, \
                len(postorder_traversal) - 1)

    # Verify if the constructed tree matches the given traversals
    if check_traversal(root, preorder_traversal, \
                       postorder_traversal):
        return root
    else:
        return None

# Example Usage:
# preorder = [1, 2, 4, 5, 3, 6, 7]
# postorder = [4, 5, 2, 6, 7, 3, 1]
# tree = construct_binary_tree_brute_force(preorder, postorder)
# print(tree)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

The very first thing we see when walking the tree in the preorder way tells us who the main boss of the entire tree is. That's the root.
Now that we know who the root is, we can look in the postorder walk to see which parts of the tree are its direct reports on the left and right sides.
The postorder walk tells us the left side's people first, then the right side's people, and lastly the root itself. This allows us to split up the rest of the nodes into left and right subtrees.
We now know the range of nodes which belong in the left and right branches. Think of it like slicing a big group into smaller teams.
Repeat the whole process again, but now focusing only on the left team, and then the right team. The first node in the preorder list of that team becomes the boss (root) of that team, and the postorder list tells you how to break up the team further.
Keep doing this until everyone is assigned to a tree node, and the tree is complete.

Code Implementation

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

def construct_from_preorder_postorder(preorder, postorder):
    preorder_index_tracker = 0

    def construct_tree(preorder_start, preorder_end, postorder_start, postorder_end):
        nonlocal preorder_index_tracker

        # If subarray is empty, there is nothing to construct
        if preorder_start > preorder_end:
            return None

        # First element of preorder is root of (sub)tree
        root_value = preorder[preorder_index_tracker]
        root_node = TreeNode(root_value)
        preorder_index_tracker += 1

        # If the (sub)tree has one element, return it
        if preorder_start == preorder_end:
            return root_node

        # Find root in postorder to determine left subtree size
        left_subtree_root_index_in_postorder = postorder.index(preorder[preorder_index_tracker])

        # Size of left subtree
        nodes_in_left_subtree = left_subtree_root_index_in_postorder - postorder_start + 1
        
        # Construct the left subtree
        root_node.left = construct_tree(
            preorder_index_tracker, preorder_index_tracker + nodes_in_left_subtree - 1,
            postorder_start, left_subtree_root_index_in_postorder
        )

        #Advance preorder index for right subtree construction
        preorder_index_tracker += nodes_in_left_subtree

        # Construct the right subtree
        root_node.right = construct_tree(
            preorder_index_tracker, preorder_end,
            left_subtree_root_index_in_postorder + 1, postorder_end - 1
        )
        # Return the constructed tree
        return root_node
    
    #Driver Function
    root = construct_tree(0, len(preorder) - 1, 0, len(postorder) - 1)
    return root

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty preorder or postorder array	Return null, as an empty tree cannot be constructed.
Preorder and postorder arrays have different lengths	Throw an exception because a valid tree cannot be constructed from inconsistent traversals.
Preorder and postorder arrays contain different sets of values	Throw an exception as the tree structure cannot be consistent with both traversals.
Single element arrays	Create a single-node tree with the element as the root.
Arrays with two elements	Create a root node with the first element of preorder, and a left child with the second element (preorder[1] must equal postorder[0]).
All elements in the arrays are identical	The resulting tree will be a skewed tree, handled correctly by the recursive construction.
Large input arrays potentially leading to stack overflow due to deep recursion	Ensure your code is tail-recursive or consider transforming the recursive algorithm into an iterative one.
The given preorder and postorder traversals do not represent a valid binary tree	Return null (or throw an exception) if at any point the construction process violates the properties of preorder/postorder traversal.